Pagini recente » Cod sursa (job #3191699) | Cod sursa (job #1860403) | Cod sursa (job #638809) | Cod sursa (job #534686) | Cod sursa (job #2162685)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
struct str{
int nod,retea;
};
vector <str> v[1000];
int mi,viz[1000],tot=0,n;
void dfs(int st)
{
viz[st]=1;
for(int i=0;i<v[st].size();i++)
{
if(viz[v[st][i].nod]==0&&v[st][i].retea>0)
{
if(v[st][i].retea<mi)
mi=v[st][i].retea;
if(v[st][i].nod==n)
{
viz[n]=1;
return;
}
dfs(v[st][i].nod);
}
if(viz[n]==1)
return;
}
}
void cd(int st)
{
viz[st]=0;
for(int i=0;i<v[st].size();i++)
{
if(viz[v[st][i].nod]==1)
{
v[st][i].retea=v[st][i].retea-mi;
cd(v[st][i].nod);
}
}
}
int main()
{
int x,i,c,y,m;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y>>c;
v[x].push_back({y,c});
}
while(mi!=10000)
{
mi=10000;
dfs(1);
cd(1);
if(mi!=10000)
tot=tot+mi;
}
g<<tot;
return 0;
}