当前位置:网站首页>P2604 [ZJOI2010]网络扩容(MCMF)

P2604 [ZJOI2010]网络扩容(MCMF)

2021-08-10 08:43:32 wx6110fa547fd20

P2604 [ZJOI2010]网络扩容(MCMF)

思路:第一问求最大流跑 d i n i c dinic dinic即可。

第二问转换为每条边容量无限,新建一个源点到 1 1 1容量为 k k k,然后跑 M C M F MCMF MCMF得到 M F MF MF即可,这里我是 E K EK EK上跑 s p f a spfa spfa实现。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=3e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,m,k,h[N],cnt=1,d[N],f[N],pre[N],dep[N],st,ed,cur[N],vis[N];
struct edge{
	int to,nt,w,c;
}e[M];
void add(int u,int v,int w,int c){
	e[++cnt]={v,h[u],w,c},h[u]=cnt;
}
bool bfs(){
	queue<int>q;q.push(st),mst(dep,0),dep[st]=1;
	while(!q.empty()){
		int  u=q.front();q.pop();cur[u]=h[u];
		for(int i=h[u];i;i=e[i].nt){
			int v=e[i].to,w=e[i].w;
			if(w&&!dep[v]) dep[v]=dep[u]+1,q.push(v);
		}
	}return dep[ed];
}
int dfs(int u,int c){
	if(u==ed) return c;int res=c;
	for(int &i=cur[u];i;i=e[i].nt){
		int v=e[i].to,w=e[i].w;
		if(w&&dep[v]==dep[u]+1){
			int now=dfs(v,min(res,w));
			if(!now) dep[v]=1;
			else e[i].w-=now,e[i^1].w+=now,res-=now;
		}if(!res) return c;
	} return c-res;
}
bool spfa(){
	queue<int>q;mst(pre,0),q.push(st),mst(d,0x3f),d[st]=0;mst(vis,0),vis[st]=1;
	f[st]=inf;
	while(!q.empty()){
		int u=q.front();q.pop(),vis[u]=0;
		for(int i=h[u];i;i=e[i].nt){
			int w=e[i].w,c=e[i].c,v=e[i].to;
			if(w&&d[v]>d[u]+c){
				d[v]=d[u]+c,f[v]=min(f[u],w);
				pre[v]=i;
				if(!vis[v]) q.push(v),vis[v]=1;
			}
		}
	}return pre[ed];
}
int dfs(){
	int ans=0,w=0;
	while(spfa()){
		w=f[ed];
		ans+=d[ed]*f[ed];
		int u=ed;
		while(u!=st){
			e[pre[u]].w-=w;
			e[pre[u]^1].w+=w;
			u=e[pre[u]^1].to; 
		}
	}return ans;
}
struct E{
	int u,v,w,c;
}a[N*5];
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].w,&a[i].c);
		add(a[i].u,a[i].v,a[i].w,0),add(a[i].v,a[i].u,0,0);
	}int mf=0;st=1,ed=n;
	while(bfs()) mf+=dfs(st,inf);printf("%d ",mf);
	st=n+1,add(st,1,k,0),add(1,st,0,0);
	for(int i=1;i<=m;i++){
		add(a[i].u,a[i].v,inf,a[i].c),add(a[i].v,a[i].u,0,0);
	}printf("%d\n",dfs());
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
  • 79.
  • 80.
  • 81.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328407

随机推荐