wa了两个
查看原帖
wa了两个
378520
河上的九酱楼主2021/1/20 21:22

刚学网络流,随便写的,


没想到错误方法都能混80

Code

#include<bits/stdc++.h>
using namespace std;

int n,m,ss,t;
int e[3001][3001],s[20001],book[10001],ans,top,flag,mi;

void dfs(int x) {
	if(x==t) {
		s[++top]=t;
		flag=1;
		mi=99999999;
		for(int i=1; i<top; i++) {
			int x,y;
			x=s[i];
			y=s[i+1];
			mi=min(mi,e[x][y]);
		}
		for(register int i=1; i<top; i++) {
			int x,y;
			x=s[i];
			y=s[i+1];
			e[x][y]-=mi;
			e[y][x]+=mi;
		}
		ans+=mi;
		return;
	}
	if(book[x]==1)
		return;
	book[x]=1;
	s[++top]=x;

	for(int i=1; i<=n; i++) {
		if(e[x][i]>0) {
			dfs(i);
		}
	}
	top--;
	return ;
}


int main() {
	cin>>n>>m>>ss>>t;
//	while(~scanf("%d %d %d %d",&n,&m,&s,&t)) {
	for(register int i=1; i<=m; i++) {
		int u,v;
		cin>>u>>v;
		e[u][v]=1;
		e[v][u]=1 ;
	}
	while(1)

	{
		memset (book ,0,sizeof book);
		top=0,flag=0;
		dfs(ss);
		if(flag==0)
			break;
	}

	cout<<ans<<endl;
	return 0;
//	}


//	return 0;
}

2021/1/20 21:22
加载中...