# Cod sursa(job #1197477)

Utilizator Data 12 iunie 2014 10:20:35 Traseu 100 cpp done Arhiva de probleme 3.01 kb
``````#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <bitset>

#define INF 0x3f3f3f3f
#define Nmax 80
#define pb push_back
#define mp make_pair
#define super_start 70
#define super_sink 71

using namespace std;

struct muchie{
int x,y;
int cost;
int capacity;
int flux;
muchie()
{
x = y = cost = capacity = flux = 0;
}
};
bitset<Nmax> inQ;
queue<int> Q;
vector<muchie> edge;
vector<pair<int,int> > G[Nmax];
int GI[Nmax],GO[Nmax];

void insert_edge(int a,int b,int cap,int cst)
{
muchie m;
m.x = a;
m.y = b;
m.capacity = cap;
m.cost = cst;
G[a].pb(mp(b,edge.size()));
edge.pb(m);
}
int N,M;

{
scanf("%d%d",&N,&M);
int a,b,c;
for(int i = 1; i <= M; ++i)
{
scanf("%d%d%d",&a,&b,&c);
GI[b]++;
GO[a]++;
insert_edge(a,b,INF,c);
insert_edge(b,a,0,-c);
}
for(int i = 1; i <= N; ++i)
{
if(GO[i] < GI[i])
{
insert_edge(super_start,i,GI[i]-GO[i],0);
insert_edge(i,super_start,GI[i]-GO[i],0);
}
if(GO[i] > GI[i])
{
insert_edge(i,super_sink,GO[i]-GI[i],0);
insert_edge(super_sink,i,GO[i]-GI[i],0);
}
}
}

bool bellman_ford()
{
memset(DP,INF,sizeof(DP));DP[super_start] = 0;
Q.push(super_start);
int k;
while(!Q.empty())
{
k = Q.front();Q.pop();inQ[k] = 0;
if(k == super_sink) continue;
for(vector<pair<int,int> >::iterator it = G[k].begin(); it != G[k].end(); ++it)
if(DP[it->first] > DP[k] + edge[it->second].cost &&
edge[it->second].capacity - edge[it->second].flux > 0)
{
DP[it->first] = DP[k] + edge[it->second].cost;
if(inQ[it->first])continue;
inQ[it->first] = 1;
Q.push(it->first);
}
}
return (DP[super_sink] != INF);
}

void FLOW()
{
int minCOST = 0, minFLOW, maxFLOW = 0;
while(bellman_ford())
{
if(DP[super_sink] == INF) continue;
minFLOW = INF;
for(int nodc = super_sink; nodc != super_start; nodc = edge[daddy[nodc]].x + edge[daddy[nodc]].y - nodc)
if(!minFLOW)continue;
for(int nodc = super_sink; nodc != super_start; nodc = edge[daddy[nodc]].x + edge[daddy[nodc]].y - nodc)
{
}
minCOST += minFLOW * DP[super_sink];
maxFLOW += minFLOW;
}