Marriage Match IV（最短路+网络流）

题意：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