UVALive 4949 Risk（二分网络流、SAP）
n个区域，每个区域有我方军队a，a==0的区域表示敌方区域，输入邻接矩阵。问经过一次调兵，使得我方边界处（与敌军区域邻接的区域）士兵的最小值最大。输出该最大值。调兵从i->j仅当a>0&&a>0&&adj==true;感觉有点像玩三国志什么的。。。赛后才知道是网络流。。网络流的构图真妙。。。给我方建个超级基地，然后把敌方的区域合并成汇点。。
从超级基地连一条边到我方所有区域，流量为a-1，限流该区域的答案，然后i->i+n，流量为a，用于可能的分配士兵，还有就是i+n->j（a&&a&&adj），流量为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, pre, gap, arc, f, cap;
19 int first, nxt, vv, e;
20
21 inline void add(int u,int v,int c) {
22 vv = v, cap = c, nxt = first, first = e++;
23 vv = u, cap = 0, nxt = first, first = e++;
24 }
25 int sap( int s, int t, int n ) {
26 int q, j, mindis, ans = 0, head = 0, tail = 1, u, v, low;
27 bool found, vis;
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 = t; vis = true; dis = 0; gap = 1;
34 while( head < tail ) {
35 u = q;
36 for( int i = first; i != -1; i = nxt ) {
37 v = vv;
38 if( !vis ) {
39 dis = dis + 1;
40 vis = true;
41 q = v;
42 gap]++;
43 arc = first;
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] == dis-1 && cap > f ) {
52 found = true; v = vv;
53 low = low < cap - f ? low : cap - f;
54 pre = u; u = v;
55 if( u == t ) {
56 while( u != s ) {
57 u = pre;
58 f] += low;
59 f^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] && cap > f ) {
70 mindis = dis];
71 arc = i;
72 }
73 }
74 gap]--;
75 if( gap] == 0 )
76 return ans;
77 dis = mindis + 1;
78 gap]++;
79 u = pre;
80 }
81 return ans;
82 }
83
84 char ch;
85 bool border;
86 int a;
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&&ch=='Y')border=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=='Y'&&a&&a)
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
页:
[1]