2013多校第四场 G题 ZZ的搬砖难题

虽然题目只给了起点st,和终点ed,  st,ed <= 10000.

但是只有200条边,极端情况也才200条边对应的400个顶点都不一样.

所以我们可以离散化顶点到[1,400]之间.然后跑个最大流即可.

注意本题边是单向的.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MAXN = 1e5+10;
#define MIN(a,b) (a)<(b)?(a):(b)
#define MAX(a,b) (a)>(b)?(a):(b)
int k, c, m, s, t, n, N;
int head[MAXN], idx, vh[MAXN], h[MAXN];
struct node{
    int v, f, nxt;
}edge[MAXN];

struct Tmp{
    int u, v, c;
    void input(){
        scanf("%d%d%d", &u,&v,&c);    
    }    
}test[210];
map<int,int> mp;
int st, ed;

void AddEdge( int u, int v, int f )
{
    edge[idx].v = v; edge[idx].f = f;
    edge[idx].nxt = head[u]; head[u] = idx++;
    edge[idx].v = u; edge[idx].f = 0;
    edge[idx].nxt = head[v]; head[v] = idx++;
}

void input() 
{
    scanf("%d", &m);
    int cnt = 0;
    mp.clear();    
    if( mp.count(st) == 0 ) mp[st] = ++cnt;
    if( mp.count(ed) == 0 ) mp[ed] = ++cnt;
    for(int i = 0; i < m; i++){
        test[i].input();
        if( mp.count( test[i].u ) == 0 ) mp[ test[i].u ] = ++cnt;
        if( mp.count( test[i].v ) == 0 ) mp[ test[i].v ] = ++cnt;
    }
    N = cnt;
    memset( head, 0xff, sizeof(head) ); idx = 0;
    s = mp[st]; t = mp[ed];
    for(int i = 0; i < m; i++){
        AddEdge( mp[test[i].u], mp[test[i].v], test[i].c );
        AddEdge( mp[test[i].v], mp[test[i].u], test[i].c );
    }
//    AddEdge( s, mp[st], inf );
//    AddEdge( mp[ed], t, inf );
}
int DFS(int u,int flow )
{
    if( u == t ) return flow;
    int tmp = h[u]+1, remain = flow;
    for(int i = head[u]; ~i; i = edge[i].nxt )
    {
        int v = edge[i].v;
        if( edge[i].f && h[u] == h[v]+1 )
        {
            int p = DFS( v, MIN( remain, edge[i].f ));
            edge[i].f -= p; edge[i^1].f += p; remain -= p;
            if( remain == 0 || h[s] == N ) return flow-remain;
        }
    }
    for(int i = head[u]; ~i; i = edge[i].nxt )
        if( edge[i].f ) tmp = MIN( tmp, h[ edge[i].v ] );
    if( !( --vh[ h[u] ] ) ) h[s] = N;
    else    ++vh[ h[u] = tmp+1 ];
    return flow-remain;
}
int sap()
{
    int maxflow = 0;
    memset( h, 0, sizeof(h));
    memset( vh, 0, sizeof(vh));
    vh[0] = N;
    while( h[s] < N ) maxflow += DFS( s, inf );
    return maxflow;
}
int main()
{
    while( scanf("%d%d", &st, &ed ) != EOF)
    {
        input();
        int res = sap();    
        printf("%d\n", res ); 
    }
    return 0;
}