萌新刚学OI,样例总是输出0求助!
查看原帖
萌新刚学OI,样例总是输出0求助!
342090
Lips楼主2020/8/10 17:29
#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
const int MAXN=520010;
int n,m,e,s,t,now[MAXN],head[MAXN],tot=1;
int ans,d[MAXN];
struct node
{
	int to,net,val;
};
node edge[MAXN];
inline void add(int u,int v,int w)
{
	edge[++tot].to=v;
	edge[tot].val=w;
	edge[tot].net=head[u];
	head[u]=tot;
	edge[++tot].to=u;
	edge[tot].val=0;
	edge[tot].net=head[v];
	head[v]=tot;
}
bool bfs(int s)
{ 
	for(register int i=1;i<=n;i++) d[i]=1e9;
	queue<int>q;
	q.push(s);
	d[s]=0;
	now[s]=head[s];
	while(!q.empty()) 
	{
		int u=q.front();
		q.pop();
		for(register int i=head[u];i;i=edge[i].net) {
			int v=edge[i].to;
			if(edge[i].val>0&&d[v]==1e9) 
			{
				q.push(v);
				now[v]=head[v];
				d[v]=d[u]+1;
				if(v==t) return true;
			}
		}
	}
	return false;
}
int dfs(int u,int sum) 
{
	if(u==t) return sum;
	int k,res=0;  
	for(register int i=now[u];i&&sum;i=edge[i].net) 
	{
		now[u]=i;  
		int v=edge[i].to;
		if(edge[i].val>0&&(d[v]==d[u]+1)) 
		{
			k=dfs(v,min(sum,edge[i].val));
			if(k==0) d[v]=1e9; 
			edge[i].val-=k;
			edge[i^1].val+=k;
			res+=k; 
			sum-=k; 
		}
	}
	return res;
}
int change(char c){return (int)c-64;}
int main() 
{
	scanf("%d",&n);
	s=change('A'),t=change('Z');
	for(register int i=1;i<=n;i++)
	{
		char u,v;
		int w;
		cin>>u>>v>>w;
		add(change(u),change(v),w);
	}
	
	while(bfs(s)) ans+=dfs(s,1e9);  
	printf("%d\n",ans);
	return 0;
}


2020/8/10 17:29
加载中...