COGS426 血帆海盗

发表于 | 分类于

题目

传送门
随着资本的扩大，藏宝海湾贸易亲王在卡利姆多和东部王国大陆各建立了N/2 个港口。大灾变发生以后，这些港口之间失去了联系，相继脱离了藏宝海湾贸易亲王的管辖，各自为政。利益的驱动使得每个港口都想和对岸大陆的另一个港口建立贸易合作关系，由于地理位置因素，只有存在直接到达的航线的两个港口才能建立合作，而且每个港口只与对岸一个港口建立合作，因此并不是所有的港口都能找到合作伙伴。

血帆海盗得知这一消息以后，决定对其中一条航线进行干扰性的掠夺。经过分析，血帆海盗计算出最多能有W 对港口合作。如果两个港口之间只有一条航线，而且这条航线恰好是血帆海盗要掠夺的航线，这两个港口将不能建立合作关系。血帆海盗指挥官菲尔拉伦想知道他们有几种选择，可以让地精们无法建立W 对港口。

INPUT

第1行，两个整数N,M，表示一共的港口个数和航线条数。
接下来M行，每行两个整数A,B，表示卡利姆多的港口A与东部王国的港口B之间有一条航线直接连接，其中1<=A<=N/2，N/2+1<=B<=N。

OUTPUT

一个整数，表示血帆海盗可以选择掠夺的航线条数。

解释：如果掠夺一条航线以后，地精依然可以建立起最多的W个合作关系（可以有多种），
那么这条航线是不值得掠夺的，否则就是掠夺方案之一。

SAMPLE

INPUT

8 5
1 5
1 6
2 7
3 7
4 8

OUTPUT

1

解题报告

好难啊= =，在编译器炸了的情况下生交了3遍，然后各种编译错误加不过样例= =

最小割的唯一性判定
在残余网络上跑tarjan求出所有SCC，记id[u]为点u所在SCC的编号。显然有id[s]!=id[t]（否则s到t有通路，能继续增广）。
①对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当id[u]!=id[v]；
②对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当id[u]==id[s]且id[v]==id[t]。
①<==将每个SCC缩成一个点，得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割，从中任取一个把id[u]和id[v]割开的割即可证明。
②<==：假设将(u,v)的边权增大，那么残余网络中会出现s->u->v->t的通路，从而能继续增广，于是最大流流量（也就是最小割容量）会增大。这即说明(u,v)是最小割集中必须出现的边。

然后就可以跑了= =

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
118
119
120
121
122
123
124
125
126
127
128
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,n,w;
}a[400005];
int pre[100005],tot;
inline void insert(int s,int e,int w){
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int n,m;
int ed;
int S(0),T;
int ans(0),inf(0x7fffffff);
int dis[100005];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(!dis[e]&&a[i].w){
				dis[e]=dis[k]+1;
				q.push(e);
				if(e==t)
					return true;
			}
		}
	}
	return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==T)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(dis[e]==dis[now]+1&&tmp&&a[i].w){
			f=dfs(e,my_min(tmp,a[i].w));
			if(!f){
				dis[e]=0;
				continue;
			}
			a[i].w-=f;
			a[i^1].w+=f;
			tmp-=f;
		}
	}
	return flow-tmp;
}
inline void dinic(int s,int t){
	while(bfs(s,t))
		ans+=dfs(s,inf);
}
int dfn[100005],low[100005],bl[100005],stack[100005];
int qlt,cnt,top;
bool vis[100005];
inline void tarjan(int u){
	dfn[u]=low[u]=++cnt;
	stack[++top]=u;
	vis[u]=1;
	for(int i=pre[u];i!=-1;i=a[i].n)
		if(a[i].w){
			int e(a[i].e);
			if(!dfn[e]){
				tarjan(e);
				low[u]=my_min(low[u],low[e]);
			}
			else
				if(vis[e])
					low[u]=my_min(low[u],dfn[e]);
		}
	if(low[u]==dfn[u]){
		qlt++;
		while(1){
			int tmp(stack[top--]);
			vis[tmp]=0;
			bl[tmp]=qlt;
			if(tmp==u)
				break;
		}
	}
}
inline int gg(){
	freopen("bloodsail.in","r",stdin);
	freopen("bloodsail.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	n=read(),m=read();
	ed=n>>1;
	T=n+1;
	for(int i=1;i<=m;i++){
		int x(read()),y(read());
		insert(x,y,1),insert(y,x,0);
	}
	for(int i=1;i<=ed;i++)
		insert(S,i,1),insert(i,S,0),insert(i+ed,T,1),insert(T,i+ed,0);
	dinic(S,T);//cout<<ans<<endl;
	for(int i=0;i<=n+1;i++)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=ed;i++)
		for(int j=pre[i];j!=-1;j=a[j].n)
			if(!a[j].w&&bl[i]==bl[a[j].e]&&a[j].e)
				ans--;
	printf("%d",ans);
	return 0;
}
int K(gg());
int main(){;}