[code=Cpp width=700px]/*
ID:huhu1711
LANG:C++
TASK:ditch
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<deque>
#include<cstring>
using namespace std;
int flag;
int E[201][201];
bool book[201];
deque <int> st;
int m,n;
void PrepareForDfs()
{
flag=0;
memset(book,0,sizeof(book));
st.clear();
st.push_back(n);
book[n]=true;
}
void Dfs()
{
int cur=st.back();
if(cur==1)
flag=1;
if(flag==1)
return;
for(int i=1;i<=n;i++)
if(E[cur]>0 && book==false)
{
book=true;
st.push_back(i);
Dfs();
if(flag==1)
return;
st.pop_back();
}
}
int main()
{
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
cin >> m >> n;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin >> x >> y >> z;
E[y][x]+=z;
}
int ans=0;
for(;;)
{
/*for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
cout << E[j] << ' ';
cout << endl;
}*/
PrepareForDfs();
Dfs();
if(flag==0)
break;
int first,second;
second=st.front();
int start=second;
st.pop_front();
st.push_back(second);
//cout << second << ' ';
int min=2100000000;
while(st.front()!=start)
{
first=second;
second=st.front();
//cout << second << ' ';
st.pop_front();
st.push_back(second);
if(E[first][second] < min)
min=E[first][second];
}
ans+=min;
second=st.front();
//cout << endl << ans << endl << endl;
st.pop_front();
while(!st.empty())
{
first=second;
second=st.front();
st.pop_front();
E[first][second]-=min;
E[second][first]+=min;
}
}
cout << ans << endl;
return 0;
}[/code]
复杂版:
有流量上下界的最大流最小流算法实现 |