Description
随着资本的扩大，藏宝海湾贸易亲王在卡利姆多和东部王 国大陆各建立了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
Sample Output
1
Hint
样例说明
地精做多能建立起合作关系的数量为3，掠夺(4,8)这条航线后，最多能建立的合作关系的数量减少为2。
数据规模
40%的数据满足2<=N<=200，1<=M<=1000
100%的数据满足2<=N<=100000，1<=M<=100000，保证N为偶数
Source
by BYVoid
网络流 ，连通性，二分图
题目大意,给定一个二分图,问有多少中方案能使断掉一条边后的最大匹配数减小;
首先通过Dinic求出最大流,然后在残量网络上进行tarjan缩强连通分量;
1.首先非匹配边断掉没有卵用;
2.对于一条匹配边,如果他对应的匹配的两个点在一个强连通分量中,说明这条边可以被替换掉,也没啥卵用;
这是为什么呢?
对于残量网络上,向T方向流的边都是表示没有进行匹配的边;
而向S方向流的边都是表示这条边已经匹配了;
所以如果连成了环,也就说明这个环中的匹配边和非匹配可以互相转化
可以画画图加深理解...%%%战舰狗老师
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<vector>
#define RG register
using namespace std;
typedef long long ll;
const int N=1000000;
const int Inf=19260817;
int gi()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
int head[N],nxt[N],to[N],s[N],cnt=1,S,T,n,m,sum,q[N],level[N],vis[N],F,c[N];
int dfn[N],low[N],zhan[N],tot,fr[N],tt,ans,vis2[N];
struct data{
int x,y,id;
}edge[N];
inline void Addedge(int x,int y,int z) {
to[++cnt]=y,s[cnt]=z,nxt[cnt]=head[x],head[x]=cnt;
}
inline void lnk(int x,int y,int z){
Addedge(x,y,z);Addedge(y,x,0);
}
inline bool bfs(){
for(RG int i=S;i<=T;i++) level[i]=0,vis[i]=0;
int t=0,sum=1;
q[0]=S,level[S]=1,vis[S]=1;
while(t<sum){
int now=q[t++];
if(now==T) return 1;
for(RG int i=head[now];i;i=nxt[i]){
int y=to[i];
if(level[y]==0&&s[i]){
level[y]=level[now]+1;
q[sum++]=y;
}
}
}
return 0;
}
inline int dfs(int now,int maxf){
if(now==T) return maxf;
int ret=0;
for(RG int i=head[now];i;i=nxt[i]) {
int y=to[i],f=s[i];
if(level[y]==level[now]+1&&f) {
int minn=min(maxf-ret,f);
f=dfs(y,minn);
s[i]-=f;s[i^1]+=f;ret+=f;
if(ret==maxf) break;
}
}
return ret;
}
inline void Dinic(){
while(bfs()) F+=dfs(S,99999999);
}
void tarjan(int x){
dfn[x]=low[x]=++tt;zhan[++sum]=x;
vis2[x]=1;int y;
for(int i=head[x];i;i=nxt[i]){
y=to[i];
if(s[i]){
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(vis2[y]) low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]){
tot++;
do {
y=zhan[sum--];
vis2[y]=0;fr[y]=tot;
} while(y!=x);
}
}
int main(){
n=gi(),m=gi();S=0,T=n+1;
for(int i=1;i<=m;i++){
int x=gi(),y=gi();
lnk(x,y,1);edge[i]=(data){x,y,cnt^1};
}
for(int i=1;i<=n/2;i++) lnk(S,i,1);
for(int i=n/2+1;i<=n;i++) lnk(i,T,1);
Dinic();for(int i=S;i<=T;i++) if(!dfn[i]) tarjan(i);
for(int i=1;i<=m;i++){
if(s[edge[i].id]==0&&fr[edge[i].x]==fr[edge[i].y]) ans++;
else if(s[edge[i].id]==1) ans++;
}printf("%d\n",m-ans);
return 0;
}