UVA 11248 Frequency Hopping 求割边集

我会带着你远行 2022-01-22 14:47 174阅读 0赞

## 题意：给定一个有向网络，每条边均有一个容量。问是否存在一个从点1到点N，流量为C的流，如果不存在，是否可以恰好修改一条弧的容量，使得存在这样的流。 ##

## 思路：网络流板子题，用的刘汝佳的模板，先求一次最大流，如果中途就大于等于C或者结尾大于等于C，就直接输出，如果小于C，就需要修改最小割里的弧，依次把最小割里的弧加上C再求最大流与C去比较就行了。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=101;
    struct Edge{
    	int from,to,cap,flow;
    };
    int c,sum,kase=0;
    struct node
    {
    	int u,v;
    };
    bool cmp(node c,node d)
    {
    	if(c.u==d.u)
    	return c.v<d.v;
    	return c.u<d.u;
    }
    struct Dinic
    {
    	int n,s,t;
    	vector<Edge>edges;
    	vector<int>G[maxn];
    	bool vis[maxn];
    	int d[maxn];
    	int cur[maxn];
    	void init(int n,int m)
    	{
    		this->n=n;
    		sum=0;
    	}
    	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 m=edges.size();
    		G[from].push_back(m-2);
    		G[to].push_back(m-1);
    	}
    	///bfs找增广路
    	bool BFS()
    	{
    		memset(vis,0,sizeof(vis));
    		memset(d,0,sizeof(d));
    		memset(cur,0,sizeof(cur));
    		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)
    				{
    					vis[e.to]=1;
    					d[e.to]=d[x]+1;
    					Q.push(e.to);
    				}
    			}
    		}
    		return d[t];
    	}
    	///板子 dfs更新正反流量
    	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]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
    			{
    				e.flow+=f;
    				edges[G[x][i]^1].flow-=f;
    				flow+=f;
    				a-=f;
    				if(flow+sum>=c)
    				return c;
    				if(a==0)
    				break;
    			}
    		}
    		return flow;
    	}
    	///最大流
    	int Maxflow(int s,int t)
    	{
    		this->s=s,this->t=t;
    		int flow=0;
    		while(BFS())
    		{
    			flow+=DFS(s,c);
    			if(flow+sum>=c)
    			return c;
    		}
    		return flow;
    	}
    	///最小割割边集
    	vector<int>Mincut()
    	{
    		vector<int>tmp;
    		for(int i=0;i<edges.size();i++)
    		if(vis[edges[i].from]&&!vis[edges[i].to]&&edges[i].cap>0)///满流了就是割边
    		tmp.push_back(i);
    		return tmp;
    	}
    	///每条边的容量减去最大流
    	void rebuild()
    	{
    		for(int i=0;i<edges.size();i++)
    		edges[i].cap-=edges[i].flow;
    	}
    	///清空流量
    	void flowclear()
    	{
    		for(int i=0;i<edges.size();i++)
    		edges[i].flow=0;
    	}
    	void work()
    	{
    		sum=Maxflow(1,n);
    		printf("Case %d: ",++kase);
    		if(sum>=c)
    		printf("possible\n");
    		else
    		{
    			vector<int>cut=Mincut();
    			rebuild();
    			vector<node>ans;
    			for(int i=0;i<cut.size();i++)
    			{
    				edges[cut[i]].cap=c;
    				flowclear();
    				if(sum+Maxflow(1,n)>=c)
    				ans.push_back((node){edges[cut[i]].from,edges[cut[i]].to});
    				edges[cut[i]].cap=0;
    			}
    			if(ans.size()==0)
    			printf("not possible\n");
    			else
    			{
    				sort(ans.begin(),ans.end(),cmp);
    				printf("possible option:(%d,%d)",ans[0].u,ans[0].v);
    				for(int i=1;i<ans.size();i++)
    				printf(",(%d,%d)",ans[i].u,ans[i].v);
    				printf("\n") ;
    			}
    		}
    		edges.clear();
    		for(int i=0;i<=n;i++)
    		G[i].clear();
    	}
    };
    Dinic solve;
    int main()
    {
    	int n,m,u,v,cap;
    	while(~scanf("%d%d%d",&n,&m,&c)&&n+m+c)
    	{
    		solve.init(n,m);
    		for(int i=1;i<=m;i++)
    		{
    			scanf("%d%d%d",&u,&v,&cap);
    			solve.AddEdge(u,v,cap);
    		}
    		solve.work();
    	}
        return 0;
    }