UVA12264 二分最大流,注意pdf的样例是错的

Posted by Cww97 on 2016-10-02

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52723982
这里有篇优秀的题解

=====坑点=====
注意input的输入格式,给的pdf里面有两组数据,样例输出只有一组,mdzz
样例是循环读入,mdzz,input里面写的是第一行给数据组数
狗屁不通(制杖+00)
=====vc=====
给n个点的无权无向图(n<=100),每个点有一个非负数ai。若ai==0则此点归敌方所有,若ai>0则此点归你且上面有ai个属于你的士兵。保证至少有一个属于你的点与敌方的点相邻。你可以让你的每个士兵最多移动一次,每次可以待在原地或者去到相邻的属于你的领地,但每个点至少要留1各士兵,使得最薄弱的关口尽量坚固。关口是指与敌方点相邻的点,薄弱与坚固分别指兵少与兵多。

思路:把每个点拆成两个点,一个入度,一个出度,入度向自己的和每个相邻的点的出度连一条边,容量是ai,每个点出度连一条边到汇点,容量为1,那些与敌人相邻的点再多连一条边到汇点,容量是二分的值,我们只需要二分这个值,跑一下网络流,如果满流,表示可以,否则不行。

本篇通过第二个样例讲解思路,下图是第二个样例的建图结果。

敌方的点不需要参与建图,因此图中没有6,7号点。

INF指无穷,mid指二分的中值。

Q:为何需要拆点?

A:我们希望通过拆点来实现每个士兵最多移动一次。下图中每个INF的边都是士兵移动的边,观察后可以发现如此建图士兵只能从入点移动到另一个点的出点,因此最多只能移动一次。(根据题意每次最远移动到相邻的点)

Q:为何出点需要连一条容量为1的边到汇点?

A:为了保证己方的点至少有1个士兵,观察下图 1出 与 2出 满流时说明1和2点至少1个人。

Q:为何要二分?

A:我们要让最薄弱的关口尽量坚固,就得使关口的士兵分配得尽量均匀,然而最大流的算法不能保证分配均匀,我们只好一个个的试,满载就放宽条件,不满载就严加条件,直到试出可行的最大解。

=======
有的版本是i->j+n,
有的版本是i+n->j,
还是没理解透里面的玄机,试了一下两种都过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N = 10007 ;
int n,m,army[N];
bool mat[107][107];

struct Dinic{
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
int s,t;
vector <Edge> edges;
vector < int> G[N]; //gragh
inline void AddEdge(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from, 0 ,0));
int top = edges.size();
G[from].push_back(top-2);
G[ to ].push_back(top-1);
}

bool vis[N]; //use when bfs
int d[N],cur[N];//dist,now edge,use in dfs
bool BFS(){
memset(vis,0,sizeof(vis));
queue <int> Q;
Q.push(s);d[s]=0;vis[s]=1;
while (!Q.empty()){
int x=Q.front();Q.pop();
for (int i=0;i<G[x].size();i++){
Edge &e=edges[G[x][i]];
if (vis[e.to]||e.cap<=e.flow)continue;
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
return vis[t];
}
int DFS(int x,int a){
if (x==t||a==0) return a;
int flow = 0, f;
for (int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if (d[x]+1!=d[e.to])continue;
if ((f=DFS(e.to,min(a,e.cap-e.flow)))<=0)continue;
e.flow += f;
edges[G[x][i]^1].flow-=f;//反向边
flow+=f; a-=f;
if (a==0) break;
}
return flow;
}
int maxFlow(int s,int t){
this->s=s;this->t=t;
int flow=0;
while(BFS()){
memset(cur,0,sizeof(cur));
flow += DFS(s,INF) ;
}
return flow;
}

bool check(int mid){
s = 0, t = (n<<1)+2;
edges.clear();
for (int i=0;i<=n*2+2;i++)G[i].clear();
int sum = 0;
for (int i=1;i<=n;i++)if (army[i]){
bool boder = 0;
AddEdge(s, i ,army[i]);
AddEdge(i,n+i,army[i]);
for (int j=1;j<=n;j++)if (mat[i][j]){
if (army[j])AddEdge(i,j+n,INF);
else boder = 1;
}
if(boder){sum+=mid;AddEdge(i+n,t,mid);}
else { sum ++; AddEdge(i+n,t, 1 ); }
}
return sum==maxFlow(s,t);
}
}g;


int main(){
//freopen("in.txt","r",stdin);
int T;scanf("%d",&T);
for (char ch;T--;){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&army[i]);
getchar();
for (int i=1;i<=n;getchar(),i++){
for (int j=1;j<=n;j++){
scanf("%c",&ch);
mat[i][j]=(ch=='Y');
}
}
int L=0,R=N-1,ans;
for (;L<R;){
int mid = (L +R) >> 1 ;
if (g.check(mid)){
ans = mid ;
L = mid + 1;
}else R = mid;
}
printf("%d\n",ans);
}
return 0;
}