UVALive 4949 Risk（二分网络流、SAP）

tubaobaoya3

　　n个区域，每个区域有我方军队a，a==0的区域表示敌方区域，输入邻接矩阵。问经过一次调兵，使得我方边界处（与敌军区域邻接的区域）士兵的最小值最大。输出该最大值。调兵从i->j仅当a>0&&a[j]>0&&adj[j]==true;感觉有点像玩三国志什么的。。。
　　
　　赛后才知道是网络流。。网络流的构图真妙。。。给我方建个超级基地，然后把敌方的区域合并成汇点。。
　　从超级基地连一条边到我方所有区域，流量为a-1，限流该区域的答案，然后i->i+n，流量为a，用于可能的分配士兵，还有就是i+n->j（a&&a[j]&&adj[j]），流量为inf。。。然后再把所有我方的边界区域连到汇点i->T（isBorder）。。。这个流量应该就是答案了。。。
　　所有正解就是，二分流量答案，SAP检查之。。。





  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <string>
  7 #include <vector>
  8 #include <queue>
  9 #include <set>
10 using namespace std;
11
12 #define ll long long
13 #define inf 2100000000
14 #define eps 1e-8
15 #define mn 505
16 #define me 200005
17
18 int dis[mn], pre[mn], gap[mn], arc[mn], f[me], cap[me];
19 int first[mn], nxt[me], vv[me], e;
20
21 inline void add(int u,int v,int c) {
22     vv[e] = v, cap[e] = c, nxt[e] = first, first = e++;
23     vv[e] = u, cap[e] = 0, nxt[e] = first[v], first[v] = e++;
24 }
25 int sap( int s, int t, int n ) {
26     int q[mn], j, mindis, ans = 0, head = 0, tail = 1, u, v, low;
27     bool found, vis[mn];
28     memset( dis, 0, sizeof(dis) );
29     memset( gap, 0, sizeof(gap) );
30     memset( vis, 0, sizeof(vis) );
31     memset( arc, -1, sizeof(arc) );
32     memset( f, 0, sizeof(f) );
33     q[0] = t; vis[t] = true; dis[t] = 0; gap[0] = 1;
34     while( head < tail ) {
35         u = q[head++];
36         for( int i = first; i != -1; i = nxt ) {
37             v = vv;
38             if( !vis[v] ) {
39                 dis[v] = dis + 1;
40                 vis[v] = true;
41                 q[tail++] = v;
42                 gap[dis[v]]++;
43                 arc[v] = first[v];
44             }
45         }
46     }
47     u = s; low = inf; pre = s;
48     while( dis < n ) {
49         found = false;
50         for( int &i = arc; i != -1; i = nxt )
51             if( dis[vv] == dis-1 && cap > f ) {
52                 found = true; v = vv;
53                 low = low < cap - f ? low : cap - f;
54                 pre[v] = u; u = v;
55                 if( u == t ) {
56                     while( u != s ) {
57                         u = pre;
58                         f[arc] += low;
59                         f[arc^1] -= low;
60                     }
61                     ans += low; low = inf;
62                 }
63                 break;
64             }
65         if( found )
66             continue;
67         mindis = n;
68         for(int i = first; i != -1; i = nxt ) {
69             if( mindis > dis[vv] && cap > f ) {
70                 mindis = dis[vv[j = i]];
71                 arc = i;
72             }
73         }
74         gap[dis]--;
75         if( gap[dis] == 0 )
76             return ans;
77         dis = mindis + 1;
78         gap[dis]++;
79         u = pre;
80     }
81     return ans;
82 }
83
84 char ch[111][111];
85 bool border[mn];
86 int a[111];
87 int getborder(int n){
88     memset(border,false,sizeof(border));
89     for(int i=1;i<=n;++i){
90         if(a==0)
91             for(int j=1;j<=n;++j)
92                 if(a[j]&&ch[j]=='Y')border[j]=true;
93     }
94     int ret=0;
95     for(int i=1;i<=n;++i)ret+=border;
96     return ret;
97 }
98 void build(int cap,int n){
99     memset(first,-1,sizeof(first));e=0;
100     for(int i=1;i<=n;++i)if(a)add(2*n+1,i,a-1),add(i,i+n,a);
101     for(int i=1;i<=n;++i)
102         for(int j=i+1;j<=n;++j)
103             if(ch[j]=='Y'&&a&&a[j])
104                 add(i+n,j,inf),add(j+n,i,inf);
105     for(int i=1;i<=n;++i)if(border)add(i,2*n+2,cap);
106 }
107 int main(){
108     int t;
109     scanf("%d",&t);
110     while(t--){
111         int n;
112         scanf("%d",&n);
113         for(int i=1;i<=n;++i)scanf("%d",a+i);
114         for(int i=1;i<=n;++i)scanf("%s",ch+1);
115         int cnt=getborder(n);
116         int l=0,r=10000;
117         while(l<r){
118             int mid=(l+r+1)/2;
119             build(mid,n);
120             if(sap(2*n+1,2*n+2,2*n+2)!=cnt*mid)r=mid-1;
121             else l=mid;
122         }
123         printf("%d\n",l+1);
124     }
125     return 0;
126 }
View Code