Cod sursa(job #2276638)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 5 noiembrie 2018 00:18:30
Problema Cuplaj maxim de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#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;
}