费用流消圈算法(构造残量网络)

妖狐艹你老母 2021-12-01 16:50 226阅读 0赞

建立某个时间段的残量网络，然后用消圈算法检测是否有负环 初始图是这么建的： 1.s到每个建筑的建边，容量是每个建筑的人，费用是0 2.每个建筑到每个避难所建边，容量是inf，费用是距离 3.避难所到t建边，容量是避难所的容量，费用是0 现在给定了一些建筑的人所在的避难所，等价于给出了一些增广路 那么只要把这些增广路加在初始图上，做出残量网络即可 1.s到所有建筑必定满流，所以不用考虑特殊情况，只要建立i->s的边即可 2.建筑到避难所原图上容量是inf，所以只要建立i->j,权值为距离 3.建筑i到避难所j有流量，那么残量网络j->i必定有流，权值为负距离 4.避难所j中的人数大于0，说明残量网络上t->j必定有流，权值为0 5.避难所没有满，说明残量网络上j->t必定有流，权值为0 在残量网络上找负圈，然后取负圈上两点，正向边+1，反向边-1

自己写的代码怎么都调不出来。。先放网上的记一下

#include <iostream>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <string.h>
    #include <string>
    #include <vector>
    #include <queue>
     
    #define MEM(a,x) memset(a,x,sizeof a)
    #define eps 1e-8
    #define MOD 10009
    #define INF 100000000
    #define ll __int64
    #define bug cout<<"here"<<endl
    #define fread freopen("ceshi.txt","r",stdin)
    #define fwrite freopen("out.txt","w",stdout)
     
    using namespace std;
     
    struct Edge
    {
        int to,next,cost;
    }edge[100000];
    int n,m;
    int head[300],tol;
    void addedge(int u,int v,int cost)
    {
        edge[tol].to=v;
        edge[tol].cost=cost;
        edge[tol].next=head[u];
        head[u]=tol++;
    }
    int x[110][3],y[110][3],sum[110],ans[110][110];
    int pre[300],vis[300],num[300],dis[300];
    //pre记录负环，num入队列的次数,spfa返回最先入队>n的点
    int len[110][110];
    int spfa(int s,int n)
    {
        queue<int> q;
        MEM(vis,0);
        MEM(num,0);
        for(int i=0;i<n;i++)
            dis[i]=INF;
        q.push(s);
        vis[s]=1;
        num[s]++;
        dis[s]=0;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];i!=-1;i=edge[i].next)
            {
                int v=edge[i].to;
                if(dis[u]+edge[i].cost<dis[v])
                {
                    dis[v]=dis[u]+edge[i].cost;
                    pre[v]=u;
                    if(!vis[v])
                    {
                        vis[v]=1;
                        q.push(v);
                        if(++num[v]>n)  return v;
                    }
                }
            }
        }
        return -1;
    }
     
    int main()
    {
    //    fread;
    //    int n,m;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            for(int i=0;i<n;i++)
                scanf("%d%d%d",&x[i][0],&x[i][1],&x[i][2]);
            for(int i=0;i<m;i++)
                scanf("%d%d%d",&y[i][0],&y[i][1],&y[i][2]);
            MEM(head,-1);
            tol=0;
            int s=n+m;//汇点
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    len[i][j]=abs(x[i][0]-y[j][0])+abs(x[i][1]-y[j][1])+1;
                    addedge(i,j+n,len[i][j]);
                }
            }
            MEM(sum,0);
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    scanf("%d",&ans[i][j]);
                    if(ans[i][j]!=0) addedge(j+n,i,-len[i][j]);
                    sum[j]+=ans[i][j];
                }
            }
            for(int i=0;i<m;i++)
            {
                if(sum[i]<y[i][2])  addedge(i+n,s,0);
                if(sum[i]>0)  addedge(s,i+n,0);
            }
            int id=spfa(s,s+1);
            if(id==-1) puts("OPTIMAL");
            else
            {
                puts("SUBOPTIMAL");
                int st=id;
                MEM(vis,0);
                while(1)
                {
                    if(!vis[st])
                    {
                        vis[st]=1;
                        st=pre[st];
                    }
                    else
                    {
                        id=st;
                        break;
                    }
                }
                do
                {
                    int u=pre[st],v=st;
                    if(u<n&&v>=n&&v<s)  ans[u][v-n]++;
                    if(v<n&&u>=n&&u<s)  ans[v][u-n]--;
                    st=pre[st];
                }while(st!=id);
                for(int i=0;i<n;i++)
                {
                    printf("%d",ans[i][0]);
                    for(int j=1;j<m;j++)
                        printf(" %d",ans[i][j]);
                    puts("");
                }
            }
     
        }
        return 0;
    }

转载于:https://www.cnblogs.com/zsben991126/p/10998506.html