HDU 3549 dinic

题

HDU

解

题意：最大流。

MD变量名重复果然是只有咸鱼才会做的事。

码（1856K, 156ms）

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

const int maxn = 1000 * 10 + 10, INF = 0x3f3f3f3f;
int s, t;
struct Edge
{
    int from, to, cap, flow;
};
vector<Edge> edges;
vector<int> G[maxn];
void add_edge(int from, int to, int cap)
{
    edges.push_back((Edge){from, to, cap, 0});
    edges.push_back((Edge){to, from, 0, 0});
    int m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
}

bool vis[maxn] = {false};
int d[maxn] = {0};
bool bfs()
{
    memset(vis, false, sizeof vis);
    queue<int> Q;
    d[s] = 0;
    vis[s] = true;
    Q.push(s);
    while(!Q.empty())
    {
        int x = Q.front(); Q.pop();
        for(int i = 0; i < G[x].size(); i++)
        {
            Edge &e = edges[G[x][i]];
            if(!vis[e.to] && e.flow < e.cap)
            {
                d[e.to] = d[x] + 1;
                vis[e.to] = true;
                Q.push(e.to);
            }
        }
    }
    return vis[t];
}

int cur[maxn] = {0};
int dfs(int x, int a)
{
    if(x == t || a == 0)
        return a;
    int flow = 0, f;
    for(int &i = cur[x]; i < G[x].size(); i++)
    {
        Edge &e = edges[G[x][i]];
        if(d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0)
        {
            e.flow += f;
            edges[G[x][i] ^ 1].flow -= f;
            flow += f;
            a -= f;
            if(a == 0) break;
        }
    }
    return flow;
}

int maxflow()
{
    int ans = 0;
    while(bfs())
    {
        memset(cur, 0, sizeof cur);
        ans += dfs(s, INF);
    }
    return ans;
}

int main()
{
    int tt;
    read(tt);
    for(int j = 1; j <= tt; j++)
    {
        int n, m;
        read(n, m);
        edges.clear();
        for(int i = 0; i <= n; i++)
            G[i].clear();
        while(m--)
        {
            int x, y, c;
            read(x, y, c);
            add_edge(x, y, c);
        }
        s = 1, t = n;
        printf("Case %d: %d\n", j, maxflow());
    }
    return 0;
}