HUNAN 11567 Escaping (最大流)

http://acm.hunnu.edu.cn/online/?action=problem&type=list&courseid=0&querytext=&pageno=31

一个n*n的房间,每个点可能有人和救生装备,两个n*n的矩阵,第一个代表每个点有多少个人,第二个矩阵代表每个点有多少个救生装备,然后每个人在t秒内要是找不到救生装备就会死亡,问能够逃生的最大人数。

如果当前点有人则源点和当前点相连,流量为人数,如果当前点有救生装备,则当前点和汇点相连,流量为装备的数量.

然后中间如果人和装备的最短距离小于等于t,则人和装备相连,流量为INF,因为同一条边人可以走多次.

  1 #include<iostream>
  2 #include<string.h>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<stdio.h>
  7 #include<cstdlib>
  8 using namespace std;
  9 
 10 const int mmax=12;
 11 const int inf=0x3f3f3f3f;
 12 int list[220],dis[220],gap[220],node;
 13 int source,sink,Vs;
 14 
 15 struct E
 16 {
 17     int to,c,next;
 18 }edg[10000002];
 19 
 20 void addedg(int from,int to,int value)
 21 {
 22     edg[node].to = to,  edg[node].c = value,  edg[node].next = list[from],   list[from] = node++;
 23     edg[node].to = from,edg[node].c = 0,      edg[node].next = list[to],     list[to] = node ++;
 24 }
 25 
 26 int dfs(int src,int aug)
 27 {
 28     if(src == sink) return aug;
 29     int flow = 0,mid_d = Vs-1;
 30     for(int j = list[src];j != -1; j = edg[j].next)
 31         if(edg[j].c)
 32         {
 33             if(dis[src] == dis[edg[j].to]+1)
 34             {
 35                 int t = dfs(edg[j].to,min(aug-flow,edg[j].c));
 36                 edg[j].c -= t;
 37                 edg[j^1].c += t;
 38                 flow += t;
 39                 if(dis[source] >= Vs)    return flow;
 40                 if(aug == flow) break;
 41             }
 42             mid_d = min(mid_d,dis[edg[j].to]);
 43         }
 44     if(!flow)
 45     {
 46         if(!(--gap[dis[src]]))    dis[source] = Vs;
 47         dis[src] = mid_d+1;
 48         ++gap[dis[src]];
 49     }
 50     //printf("%d
",flow);
 51     return flow;
 52 }
 53 
 54 int maxflow_sap(int src,int ed)  //1  m
 55 {
 56     int ans = 0;
 57     memset(gap,0,sizeof(gap));
 58     memset(dis,0,sizeof(dis));
 59     gap[0] = Vs = ed;
 60     source = src, sink = ed;
 61 
 62     while(dis[source] < Vs)
 63     {
 64         ans += dfs(source,inf);
 65        // printf("%d
",ans);
 66     }
 67     return ans;
 68 }
 69 
 70 int main()
 71 {
 72     //freopen("a.txt","r",stdin);
 73     int n,t;
 74     int boat[mmax][mmax];
 75     int man[mmax][mmax];
 76     while(~scanf("%d%d",&n,&t))
 77     {
 78         node = 0;
 79         memset(list,-1,sizeof(list));
 80 
 81         for(int i=0;i<n;i++)
 82         {
 83             for(int j=0;j<n;j++)
 84             {
 85                 scanf("%d",&man[i][j]);//源点和人相连
 86                 if(man[i][j]>0) addedg(2*n*n+1,i*n+j,man[i][j]);
 87                 //printf("%d ",man[i][j]);
 88             }
 89             //printf("
");
 90         }
 91         for(int i=0;i<n;i++)
 92         {
 93             for(int j=0;j<n;j++)
 94             {
 95                 scanf("%d",&boat[i][j]);//装备和汇点相连
 96                 if(boat[i][j]>0) addedg(i*n+j+n*n,2*n*n+2,boat[i][j]);
 97                 //printf("%d ",boat[i][j]);
 98             }
 99             //printf("
");
100         }
101         for(int i=0;i<n;i++)
102         {
103             for(int j=0;j<n;j++)
104             {
105                 if(man[i][j]>0)
106                 {
107                     for(int k=0;k<n;k++)
108                     {
109                         for(int p=0;p<n;p++)
110                         {
111                             if(boat[k][p]>0&&abs(k-i)+abs(p-j)<=t)
112                             {   //人与装备相连
113                                 addedg(i*n+j,k*n+p+n*n,inf);
114                                 //printf("%d %d %d %d
",i,j,k,p);
115                             }
116                         }
117                     }
118                 }
119             }
120         }
121         int ans=maxflow_sap(2*n*n+1,2*n*n+2);
122         printf("%d
",ans);
123     }
124     return 0;
125 }