我的费用流是假的吗?
查看原帖
我的费用流是假的吗?
251723
Schwarzkopf_Henkal楼主2020/12/26 16:01

RT,无O2 TLE30,有O2 TLE60,不知道原因,我的板子是在dinic上改的,是我的板子出了问题还是我的建模出了问题?

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int u,v;
    long long c,w,s;//Capacity Flow Cost
};
struct ssp{
    const static int N=100005;
    int n,m,s,t;
    vector<Edge>E;
    vector<int>to[N];
    long long dis[N],C[N],ret;//去掉了当前弧优化 | 又加上了(
    bool vis[N];
    void clear(int n){
        for(int i=1;i<=n;i++)
            to[i].clear();
        E.clear();
    }
    void AddEdge(int u,int v,long long w,long long s){
        E.push_back({u,v,w,0,s});
        E.push_back({v,u,0,0,-s});
        m=E.size();
        to[u].push_back(m-2);
        to[v].push_back(m-1);
    }
    bool spfa(){
        memset(dis,6,sizeof(dis));
        queue<int>que;
        que.push(s);
        dis[s]=0;
        vis[s]=1;
        while(!que.empty()){
            int cur=que.front();
            que.pop();
            vis[cur]=0;
            for(int i=0;i<to[cur].size();i++){
                Edge& e=E[to[cur][i]];
                if(e.c>e.w&&dis[e.v]>dis[cur]+e.s){
                    dis[e.v]=dis[cur]+e.s;
                    if(!vis[e.v]){
                        que.push(e.v);
                        vis[e.v]=1;
                    }
                }
            }
        }
        return dis[t]<=1e15;
    }
    long long dfs(int u,long long v){
        if(u==t||v==0)
            return v;
        long long w=0,f;
        vis[u]=1;
        for(int i=C[u];i<to[u].size()&&v;i++){
            C[u]=i;
            Edge& e=E[to[u][i]];
            if(!vis[e.v]&&dis[u]+e.s==dis[e.v]&&(f=dfs(e.v,min(v,e.c-e.w)))>0){
                ret+=f*e.s;
                e.w+=f;
                E[to[u][i]^1].w-=f;
                w+=f;
                v-=f;
            }
        }
        vis[u]=0;
        return w;
    }
    pair<long long,long long> MaxFaFaflow(int s,int t){
        this->s=s;
        this->t=t;
        ret=0;
        long long res=0,cur;
        while(spfa()){
            memset(C,0,sizeof(C));
            while(cur=dfs(s,1e18))
                res+=cur;
        }
        return make_pair(res,ret);
    }
}R;
int n,m,t[50][105],sum,p[50];//每个厨师拆成sum个点
int MK(int u,int v){//第u个厨师,第v道菜
    return (u-1)*sum+v;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
        sum+=p[i];
        R.AddEdge(1,i+2,p[i],0);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&t[i][j]);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=sum;j++){
            R.AddEdge(MK(i,j)+n+2,2,1,0);
            for(int k=1;k<=n;k++)
                R.AddEdge(k+2,MK(i,j)+n+2,1,j*t[k][i]);
        }
    printf("%lld",R.MaxFaFaflow(1,2).second);
}/*

*/
2020/12/26 16:01
加载中...