edmondskarp.cpp (4.1)

#include <stdio.h>
#include <string.h>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

#define long long long
#define f1(i,n) for (int i=1; i<=n; i++)
#define f0(i,n) for (int i=0; i<n; i++)
typedef pair<long, long> llll;
#define X first
#define Y second

#define N 202
int n, m, LinkSize, Pending;
vector<llll> a[N]; //
int Max[N][N], Cur[N][N]; //
int d[N], Parent[N];
long Answer = 0; //

bool minimize(int &a, int b)
    { if (a>b) a=b; else return false; return true; }

bool ford_bellman(int u, int Target){
    queue<llll> qu;
    memset(d, 0x3c, sizeof d);
    d[u]=0, Parent[u]=0; qu.push(llll(0, u));

    while (qu.size()){
        llll Top=qu.front(); qu.pop(); u=Top.Y;
        if (d[u]!=Top.X) continue;
//      printf("d[%d] = %d\n", u, d[u]);
        for (int i=0; int v=a[u][i].Y; i++)
        if (Cur[u][v]<Max[u][v]) {
            if (minimize(d[v], d[u]+(Cur[u][v]>=0?1:-1)*a[u][i].X))
            { Parent[v]=u; qu.push(llll(d[v], v)); }
        }
    }
    return d[Target]!=0x3c3c3c3c;
}

void enlarge(){
    int Min=Pending;
    for (int u=n; int p=Parent[u]; u=p)
    minimize(Min, Cur[p][u]>=0 ? Max[p][u]-Cur[p][u] : -Cur[p][u]);
    for (int u=n; int p=Parent[u]; u=p)
    { Cur[p][u]+=Min; Cur[u][p]-=Min; }

    Pending-=Min;
    Answer += 1LL*Min*d[n];
}

void enter(){
    f1(i,m) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(llll(z, y));
        a[y].push_back(llll(z, x));
        Max[x][y]++;
        Max[y][x]++;
    }
    f1(i,n) a[i].push_back(llll());
    scanf("%d%d", &Pending, &LinkSize);
    f1(i,n) f1(j,n) Max[i][j] *= LinkSize;
}

main(){
while (scanf("%d%d", &n, &m) > 0){
    enter();
    while (Pending && ford_bellman(1, n)) enlarge();
    if (Pending) cout << "Impossible." << endl;
    else cout << Answer << endl;

    f1(i,n) a[i].clear();
    memset(Cur, 0, sizeof Cur);
    memset(Max, 0, sizeof Max);
    Answer=0;
}
}