poj 2175(费用流消圈)

题意：给出n栋房子位置和每栋房子里面的人数，m个避难所位置和每个避难所可容纳人数。然后给出一个方案，判断该方案是否最优，如果不是求出一个更优的方案。

思路：很容易想到用最小费用流求出最优时间，在与原方案花费时间对比判断原方案是否最优。但是这种方法会超时的。其实还有一种复杂度更低的方法：判断原方案在费用流模型中是否有负环，如果有，将负环中的每条边流量加一就可以达到更优。

定理：一个费用流是最小费用流的充要条件是这个费用流的残量网络没有负费用圈。

（我是根据费用流模型加流实现，可以有更好的建图方法）

费用流消圈：

View Code

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<algorithm>
  5 using namespace std;
  6 #define N 1010
  7 #define M N*N
  8 #define inf 0x3f3f3f3f
  9 struct edge{
 10     int a,b,cap,flow,cost,next;
 11 }e[M];
 12 int pre[N],in[N],dist[N],p[N],q[N],a[N],b[N],num[N],pos[N][N],plan[N][N];
 13 int cnt,S,T;
 14 void add(int a,int b,int cap,int cost)
 15 {
 16     edge es={a,b,cap,0,cost,pre[a]};
 17     e[cnt]=es;
 18     pos[a][b]=cnt;
 19     pre[a]=cnt++;
 20 }
 21 bool spfa()
 22 {
 23     int rear=0,tail=1;
 24     memset(in,0,sizeof(in));
 25     memset(num,0,sizeof(num));
 26     for(int i=0;i<=T;i++)
 27     dist[i]=inf;
 28     dist[S]=0;
 29     p[S]=0;
 30     q[rear]=S;
 31     in[S]=1;
 32     while(rear<tail)
 33     {
 34         int u=q[rear%N];rear++;
 35         in[u]=0;
 36         for(int edg=pre[u];edg!=0;edg=e[edg].next)
 37         {
 38             int v=e[edg].b;
 39             if(dist[v]>dist[u]+e[edg].cost&&e[edg].cap>e[edg].flow)
 40             {
 41                 dist[v]=dist[u]+e[edg].cost;
 42                 p[v]=u;
 43                 if(!in[v])
 44                 {
 45                     in[v]=1;
 46                     q[tail%N]=v;tail++;
 47                     num[v]++;
 48                     if(num[v]>T)
 49                     {
 50                         memset(in,0,sizeof(in));
 51                         while(!in[v])
 52                         {
 53                             in[v]=1;
 54                             v=p[v];
 55                         }
 56                         int end=v;
 57                         do{
 58                             if(v>p[v]&&v!=T)plan[p[v]][v]++;
 59                             else if(p[v]>v&&p[v]!=T)plan[v][p[v]]--;
 60                             v=p[v];
 61                         }while(v!=end);
 62                         return false;
 63                     }
 64                 }
 65             }
 66         }
 67     }
 68     return true;
 69 }
 70 int main()
 71 {
 72     int n,m;
 73     while(scanf("%d%d",&n,&m)!=EOF)
 74     {
 75         S=0;T=m+n+1;cnt=2;
 76         memset(pre,0,sizeof(pre));
 77         for(int i=1;i<=n;i++)
 78         {
 79             int c;
 80             scanf("%d%d%d",&a[i],&b[i],&c);
 81             add(S,i,c,0);
 82             add(i,S,0,0);
 83         }
 84         for(int j=n+1;j<=m+n;j++)
 85         {
 86             int x,y,w;
 87             scanf("%d%d%d",&x,&y,&w);
 88             for(int i=1;i<=n;i++)
 89             {
 90                 int len=abs(a[i]-x)+abs(b[i]-y)+1;
 91                 add(i,j,inf,len);
 92                 add(j,i,0,-len);
 93             }
 94             add(j,T,w,0);
 95             add(T,j,0,0);
 96         }
 97         for(int i=1;i<=n;i++)
 98         {
 99             for(int j=n+1;j<=m+n;j++)
100             {
101                 scanf("%d",&plan[i][j]);
102                 int x=pos[i][j];
103                 e[x].flow+=plan[i][j];
104                 e[x^1].flow-=plan[i][j];
105                 x=pos[j][T];
106                 e[x].flow+=plan[i][j];
107                 e[x^1].flow-=plan[i][j];
108             }
109         }
110         if(spfa())printf("OPTIMAL\n");
111         else {
112             puts("SUBOPTIMAL");
113             for(int i=1;i<=n;i++){
114                 for(int j=n+1;j<m+n;j++)
115                 printf("%d ",plan[i][j]);
116                 printf("%d\n",plan[i][m+n]);
117             }
118         }
119     }
120     return 0;
121 }