UVA 10480 Sabotage(最小割)

Description

N个城市，M条连接城市的边，现在要切断城市1与城市2间的联络，求最小费用

Attention

一般的网络流知道了S(源点)T(汇点)，就默认了流向，所以路是单向的(两条边,w+0)

但这题不同，两城市是等价的，都是S都是T，所以路是双向的(两条边,w+w)

若是已知唯一的S(源点)T(汇点)，而题目又暗示(或明示)路是双向的(四条边w+0+w+0)

Code

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define Close ios::sync_with_stdio(false);

const int N = 805;

ll n, m, maxflow, deep[N], u[N], v[N];

struct edge
{
    ll to, w, pre;
} a[200005];

int cnt = -1;
ll head[N], start, over, q[N], fro, bac;

///网络流中的单向边实际是添加两条边的
///那么双向边对应实际添加四条边
void add(int from, int to, int w)
{
    a[++cnt].to = to;
    a[cnt].pre = head[from];
    a[cnt].w = w;
    head[from] = cnt;
    a[++cnt].to = from;
    a[cnt].pre = head[to];
    a[cnt].w = w;
    head[to] = cnt;
}

bool bfs()
{
    memset(deep, -1, sizeof(deep));
    fro = bac = 0;
    q[bac++] = start, deep[start] = 0;

    while(fro < bac)
    {
        ll first = q[fro++];
        for(int i = head[first]; i != -1; i = a[i].pre)
        {
            ll v = a[i].to;
            if(deep[v] < 0 && a[i].w > 0)
            {
                deep[v] = deep[first] + 1;
                q[bac++] = v;
            }
        }
    }
    return deep[over] > 0;
}

ll DFS(ll s, ll cap)
{
    if(s == over)
        return cap;

    ll f;
    for(int i = head[s]; i != -1; i = a[i].pre)
    {
        ll to = a[i].to;
        if(a[i].w > 0 && deep[to] == deep[s] + 1 && (f = DFS(to, min(cap, a[i].w))) )
        {
            a[i].w -= f;
            a[i ^ 1].w += f;
            return f;
        }
    }
    deep[s] = -1;
    return 0;
}


void Dinic()
{
    ll temp;
    while(bfs())
        while((temp = DFS(start, INF)) > 0)
            maxflow += temp;
}

int main()
{
    while(~scanf("%lld%lld", &n, &m))
    {
        if(n == 0 && m == 0)
            break;
        ll cost;
        start = 1, over = 2;
        memset(head, -1, sizeof(head));
        memset(u, 0, sizeof(u));
        memset(v, 0, sizeof(v));
        cnt = -1, maxflow = 0;
        for(int i = 0; i < m; ++i)
        {
            scanf("%lld%lld%lld", &u[i], &v[i], &cost);
            add(u[i], v[i], cost);
        }
        Dinic();
        for(int i = 0; i < m; ++i)
        {
            if((deep[ u[i] ] < 0 && deep[ v[i] ] >= 0) 
               || (deep[ v[i] ] < 0 && deep[ u[i] ] >= 0))
                cout << u[i] << ' ' << v[i] << '\n';
        }
        cout << '\n';
    }
    return 0;
}