BZOJ_2561_最小生成树_最小割
题意： 给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？
分析：
如果所有边中有能使u，v连通且权值比L小的，那新加的这条边就不会出现在最小生成树上，最大生成树同理，那么问题就转化成求u，v之间的最小割，最小和最大分别做一次，相加即可。
注意无向图连边时容量。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define N 20020
#define M 400050
#define inf 100000000
struct A
{
int a,b,v;
}e[M];
int S,T,ans;
int head[N],to[M],nxt[M],cnt=1,flow[M],n,m;
int dep[N];
void add(int u,int v,int f)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
flow[cnt]=f;
}
bool bfs()
{
queue <int> q;
memset(dep,0,sizeof(dep));
dep[S]=1;q.push(S);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i])
{
if(!dep[to[i]]&&flow[i])
{
dep[to[i]]=dep[x]+1;
if(to[i]==T)return 1;
q.push(to[i]);
}
}
}
return 0;
}
int dfs(int x,int mf)
{
if(x==T)return mf;
int nf=0;
for(int i=head[x];i;i=nxt[i])
{
if(dep[to[i]]==dep[x]+1&&flow[i])
{
int tmp=dfs(to[i],min(flow[i],mf-nf));
nf+=tmp;
flow[i]-=tmp;
flow[i^1]+=tmp;
if(nf==mf)break;
}
}
dep[x]=0;
return nf;
}
int dinic()
{
int f,sum=0;
while(bfs())
{
while(f=dfs(S,inf))
{
sum+=f;
}
}
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
}
scanf("%d%d%d",&S,&T,&z);
for(int i=1;i<=m;i++)
{
if(e[i].v<z)
{
add(e[i].a,e[i].b,1);
add(e[i].b,e[i].a,1);
}
}
ans+=dinic();
memset(head,0,sizeof(head));
cnt=1;
for(int i=1;i<=m;i++)
{
if(e[i].v>z)
{
add(e[i].a,e[i].b,1);
add(e[i].b,e[i].a,1);
}
}
printf("%d",ans+dinic());
}