蜜汁wa啊啊啊,只有54分,还T了几个点
查看原帖
蜜汁wa啊啊啊,只有54分,还T了几个点
70081
尹昱钦楼主2020/9/4 19:26
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=5005;
const int maxm=50005;
int n,m,s,t,flow[maxn],dis[maxn],pre[maxn],vis[maxn],last[maxn];
int p[maxn],cnt=-1;
long long ansflow,anscost;
struct node{
	int v,next,cap,flow,w;
}e[maxm*2];
void insert(int u,int v,int w,int cap){
	cnt++;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].cap=cap;
	e[cnt].flow=0;
	e[cnt].next=p[u];
	p[u]=cnt;
}
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	memset(flow,0x3f,sizeof(flow));
	memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(s);
	pre[t]=-1;
	dis[s]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=p[u];i!=-1;i=e[i].next){
			if(e[i].cap-e[i].flow<=0) continue;
			if(dis[e[i].v]>dis[u]+e[i].w){
				dis[e[i].v]=dis[u]+e[i].w;
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
				pre[e[i].v]=u;
				last[e[i].v]=i;
				flow[e[i].v]=min(flow[u],e[i].cap-e[i].flow);
			}
		}
	}
	return pre[t]!=-1;
}
void mcmf(){
	while(spfa()){
		ansflow+=flow[t];
		anscost+=dis[t]*flow[t];
		int now=t;
		while(now!=s){
			e[last[now]].flow+=flow[t];
			e[last[now]^1].flow-=flow[t];
			now=pre[now];
		}
	}
	cout<<ansflow<<" "<<anscost;
}
int main(){
	memset(p,-1,sizeof(p));
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w,f;
		scanf("%d%d%d%d",&u,&v,&w,&f);
		insert(u,v,w,f);
		insert(v,u,-w,0); 
	}
	mcmf();
	return 0;
} 
2020/9/4 19:26
加载中...