欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Marriage Match IV(最短路+网络流)

程序员文章站 2022-04-22 20:51:25
题意:N个点M条边的有向图,给定起点S和终点T,求每条边都不重复的S–>T的最短路有多少条。第一步:求出最短路若d[u]+w == d[v]。那么e就是最短路上的一条边。spfa会被卡常,建议改用dijikstra第二步:求出最大流每条边都不重复的××,老网络流模型了求解S到T的最大流。将所求得的最短路的边,建新图,每条边的流量都是1。再用dinik求出S到T的最大流,即最终答案。code:#include#define ll long lo...

题意:N个点M条边的有向图,给定起点S和终点T,求每条边都不重复的S–>T的最短路有多少条。

第一步:求出最短路

若d[u]+w == d[v]。那么e就是最短路上的一条边。
spfa会被卡常,建议改用dijikstra

第二步:求出最大流

每条边都不重复的××,老网络流模型了
求解S到T的最大流。将所求得的最短路的边,建新图,每条边的流量都是1。再用dinik求出S到T的最大流,即最终答案。
code:

#include<bits/stdc++.h>
#define ll long long
#define inf 2005020600
#define me(x) memset(x,0,sizeof x)
using namespace std;
int n,m,s,t;
struct n{
	int w,to,from;
}edge[200010];//链式前向星 
struct node{	
	int pos;
	int dis;
	bool operator <(const node &a)const
	{
		return a.dis<dis;//小根堆 
	}
};
class Disk{
	public:		
		int head[1010];
		int cnt,dis[1010],vis[1010];
		priority_queue<node>q;
		void init()
		{
			me(head);me(dis);me(vis);
			me(edge);cnt = 0;
		}
		void add(int u,int v,int w){
			cnt++;
			edge[cnt].w=w;
			edge[cnt].to=v;
			edge[cnt].from=head[u];
			head[u]=cnt;
		}
		void dijk(int s)
		{
			for(int i=1;i<=n;i++)
			dis[i]=0x3f3f3f3f;//初始化dis 
			dis[s]=0;
			q.push((node){s,0});
			while(!q.empty()){
				node sign=q.top();//最适合的点自动上浮 
				q.pop();
				int x=sign.pos;int d=sign.dis;
				if(vis[x]) continue;
				vis[x]=1;
				for(int i=head[x];i;i=edge[i].from){
					int y=edge[i].to;
					if(dis[y]>dis[x]+edge[i].w)
					{
						dis[y]=dis[x]+edge[i].w;
						if(!vis[y]) q.push((node){y,dis[y]});//可更新的点压入队列 
					}						
				}
			}
		}
}disk;
struct nod{
	int to,from;
	ll w;
}edge2[200007];
class dilink{
	public:
		int head[2007],now[2007],cnt=1;
		ll dep[2007],ans;
		void init()
		{
			me(head);me(now);me(dep);me(edge2);
			cnt = 1;ans = 0;
		}
		void add(int u,int v,ll w)
		{
			cnt++;
			edge2[cnt].to = v;
			edge2[cnt].w = w;
			edge2[cnt].from = head[u];
			head[u] = cnt;
		}
		int bfs()
		{
			for(int i=1;i<=n;i++)
				dep[i] = inf;
			queue<int>q;
			q.push(s);
			dep[s] = 0;
			now[s] = head[s];
			while(!q.empty())
			{
				int so = q.front();
				q.pop();
				for(int i=head[so];i;i=edge2[i].from)
				{
					int to = edge2[i].to;
					if(edge2[i].w&&dep[to] == inf)
					{
						q.push(to);
						now[to] = head[to];
						dep[to] = dep[so]+1;
						if(to==t) return 1;
					}
				}
			}
			return 0;
		}
		int dfs(int x,ll sum)
		{
			if(x==t)return sum;
			ll k,res=0;
			for(int i=now[x];i&&sum;i = edge2[i].from)
			{
				now[x] = i;//当前弧优化
				int to = edge2[i].to;
				if(edge2[i].w&&dep[to]==dep[x]+1)
				{
					k = dfs(to,min(sum,edge2[i].w));
					if(k==0) dep[to] = inf;
					edge2[i].w-=k;
					edge2[i^1].w+=k;
					res+=k;//流量和 
					sum-=k;//剩余流量 
				} 
			}
			return res;
		}
		int dini(){
			while(bfs())ans+=dfs(s,inf);
			return ans;
		}
}di;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		disk.init();
		di.init();
		cin>>n>>m;
		
		for(int i=1;i<=m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			disk.add(a,b,c);
//			disk.add(b,a,c);
		}
		scanf("%d%d",&s,&t);
		disk.dijk(s);
		for(int i = 1;i<=n;i++)
		{
			for(int j =disk.head[i];j;j = edge[j].from )
			{
				int to = edge[j].to;
				if(disk.dis[to] == disk.dis[i]+edge[j].w)
				{
					di.add(i,to,1);
					di.add(to,i,0);
				}
			}
		}
		cout<<di.dini()<<endl;
	}
}

本文地址:https://blog.csdn.net/naiue/article/details/107587368

相关标签: ACM 算法