hdu6214 Smallest Minimum Cut(网络流-最小割的最小边集)_网络流 minimum-cut

题目

给定一张点数n(n<=200)和边数m(m<=1000)的图

求这张图最小割时，割掉的那些边的边数最少是多少

题解

其实自己之前这题做过，学最大权闭合子图的时候学过

然后这有个方法就是把边权放大，

比如w=10000w+1，然后再跑最小割，

原来相同最小割的边集再求最小割的时候，

会在边权放大之后有边数上的差别，

所以就是加的少的跑出来是新图的最小割，

也是我们想要的加的边少的最小割

然后把答案对10000取模，就是加的边数

除以10000向下取整，就是原来的最小割，

这个10000的下界是m+1，

不然边数带来的贡献会和一条边的权值搞混

心得

要总结只是因为Dinic板子被卡了，体验极差

感谢涛神提供的Dinic优化板子，其实只加了一行

队列的地方，如果怕动态开内存爆内存或爆时间，可以用数组模拟

从1995ms跑到170ms，强得一匹

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map> 
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3fll;
const int maxn=210;
const int maxm=2e3+10;
int level[maxn];
int head[maxn],cnt;
int t,n,m;
int ss,ee;
struct edge{int v,nex;ll w;}e[maxm];
void init()
{
	cnt=0;
	memset(head,-1,sizeof head);
}
void add(int u,int v,ll w)
{
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
bool bfs(int s,int t)
{
	queue<int>q;
	memset(level,0,sizeof level);
	level[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		if(x==t)return 1;
		for(int u=head[x];~u;u=e[u].nex)
		{
			int v=e[u].v;ll w=e[u].w;
			if(!level[v]&&w)
			{
				level[v]=level[x]+1;
				q.push(v);
			}
		}
	}
	return 0;
}
ll dfs(int u,ll maxf,int t)
{
	if(u==t)return maxf;
	ll ret=0;
	for(int i=head[u];~i;i=e[i].nex)
	{
		int v=e[i].v;ll w=e[i].w;
		if(level[u]+1==level[v]&&w)
		{
			ll MIN=min(maxf-ret,w);
			w=dfs(v,MIN,t);
			e[i].w-=w;
			e[i^1].w+=w;
			ret+=w;
			if(ret==maxf)break;
		}
	}
	if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了 
	return ret;
}
ll Dinic(int s,int t)
{
	ll ans=0;
	while(bfs(s,t))
	ans+=dfs(s,INF,t);
	return ans;
}
int main()
{ 
    scanf("%d",&t);
    //n个点 m条边 
    while(t--)
    {
    	init();
    	scanf("%d%d",&n,&m);
    	scanf("%d%d",&ss,&ee);
    	ss--,ee--;
    	for(int j=0;j<m;++j) 
    	{
    		int u,v;ll w;
    		scanf("%d%d%lld",&u,&v,&w);
    		u--,v--;
    		w=w*10000+1;
    		add(u,v,w);
    		add(v,u,0);//有向图反向边权为0 无向图反向边权为w 
    	}
    	ll ans=Dinic(ss,ee);
    	printf("%lld\n",ans%10000);
    }
	return 0;
}