Pagini recente » Cod sursa (job #162122) | Cod sursa (job #2839997) | Cod sursa (job #2593923) | Cod sursa (job #1875222) | Cod sursa (job #2276638)
#include <bits/stdc++.h>
const int oo=1e9;
using namespace std;
ifstream f("cmcm.in");
ofstream g("cmcm.out");
int n,m,i,e,x,y,z,ans1,ans2,cost[610][610],cap[610][610];
pair<int,int> u[50010];
vector<int> v[610];
bool bell()
{
queue<int> Q;
int dist[610],tata[610];
bitset<610> in;in.reset();
for(i=0;i<=n+m+1;i++)dist[i]=oo;
Q.push(0);dist[0]=0;
while(Q.size())
{
int x=Q.front();
Q.pop();in[x]=0;
for(auto it:v[x])
if(cap[x][it]&&(dist[it]>dist[x]+cost[x][it]))
{
dist[it]=dist[x]+cost[x][it];
if(!in[it])
{
Q.push(it);
in[it]=1;
}
tata[it]=x;
}
}
if(dist[n+m+1]==oo)return 0;
int flux=oo;
for(int nod=n+m+1;nod;nod=tata[nod])
flux=min(flux,cap[tata[nod]][nod]);
for(int nod=n+m+1;nod;nod=tata[nod])
{
cap[tata[nod]][nod]-=flux;
cap[nod][tata[nod]]+=flux;
}
ans1+=flux;ans2+=flux*dist[n+m+1];
return 1;
}
int main()
{
// clock_t t;
// t = clock();
// cout<<((float)t)/CLOCKS_PER_SEC<<'\n';
f>>n>>m>>e;
for(i=1;i<=e;i++)
{
f>>x>>y>>z;
v[x].push_back(y+n);
v[y+n].push_back(x);
u[i]={x,y};
cost[x][y+n]=z;
cost[y+n][x]=-z;
cap[x][y+n]=1;
}
for(i=1;i<=n;i++)
{
v[0].push_back(i);
cap[0][i]=1;
}
for(i=n+1;i<=n+m;i++)
{
v[i].push_back(n+m+1);
cap[i][n+m+1]=1;
}
for(;bell(););
g<<ans1<<' '<<ans2<<'\n';
// for(i=1;i<=e;i++)
// if(cap[u[i].first][u[i].second+n]==0)
// g<<i<<' ';
// t = clock() - t;
// cout<<((float)t)/CLOCKS_PER_SEC<<'\n';
return 0;
}