uva 10983 Buy one, get the rest free 二分判定层次图

二分枚举租用飞机的最大花费,然后用小于等于最大花费的边构建层次图(依据时间)

构图思路:   利用二元组(x,y)表示 x天y城市

　　1. e天有飞机从a城市飞到b城市，能够承载x人，则添加单向边 ( e, a ) -> ( e+1, b ) 容量为x

　　2. 每一天的a城市到第二天的a城市连边，容量为正无穷大

　　3. 每一天的N城市到汇点T连边，容量为正无穷大

　　4. 源点V与第0天的所有顶点连边，容量为当前城市0天初始人数

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<string>

#include<queue>

#include<vector>

using namespace std;

const int M = ;

const int inf = 0x3f3f3f3f;

int n, d, m, tot;

struct Fight{

    int u, v;

    int c, p, e;

    void input(){

        scanf("%d%d%d%d%d",&u,&v,&c,&p,&e);

    }

}fight[M];

int people[];

int S, T, N;

struct Edge{

    int v, f, nxt;

}edge[];

int head[], idx;

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 = ;

    edge[idx].nxt = head[v], head[v] = idx++;

}

void CreateGraph(int Max){

    //init

    idx = ;

    memset( head, -, sizeof(head));

    S = , T = (d+)*n+, N = (d+)*n+;

    int u, v, c, p, e;

    for(int i = ; i < m; i++){

        u = fight[i].u, v = fight[i].v, c = fight[i].c, p = fight[i].p, e = fight[i].e;

        if( p <= Max ) AddEdge( e*n+u, (e+)*n+v, c );

    }

    for(int i = ; i <= n; i++ )

        AddEdge( S, i, people[i] );

    for(int d1 = ; d1 < d; d1++ ){

        for(int i = ; i <= n; i++ )

            AddEdge( d1*n+i, (d1+)*n+i, inf );

    }

    for(int d1 = ; d1 <= d; d1++ )

        AddEdge( d1*n+n, T, inf );

}

int h[], vh[];

int dfs(int u, int flow ){

    if( u == T ) return flow;

    int t = h[u]+, sum = flow;

    for(int i = head[u]; ~i; i = edge[i].nxt ){

        int v = edge[i].v;

        if( edge[i].f && (h[v]+==h[u]) ){

            int tmp = dfs( v, min(sum,edge[i].f) );

            edge[i].f -= tmp, edge[i^].f += tmp; sum -= tmp;

            if( sum ==  || h[S] == N ) return flow-sum;

        }

    }

    for(int i = head[u]; ~i; i = edge[i].nxt )

        if( edge[i].f ) t = min( t, h[ edge[i].v ] );

    if( --vh[ h[u] ] ==  ) h[S] = N;

    else ++vh[ h[u] = t+ ];

    return flow - sum;

}

int sap(){

    int maxflow = ;

    memset( h, , sizeof(h));

    memset( vh, , sizeof(vh));

    vh[] = N;

    while( h[S] < N ) maxflow += dfs( S, inf );

    return maxflow;

}

int solve(){

    int ans = -;

    int l = , r = ;

    while( l <= r ){

        int mid = (l+r)>>;

        CreateGraph( mid );

        int tmp = sap(); //printf("tmp = %d\n", tmp);

        if( tmp >= tot ) ans = mid, r = mid-;

        else l = mid+;

    }

    return ans;

}

int main(){

    int _;

    scanf("%d",&_);

    for(int Case = ; Case <= _; Case++){

        scanf("%d%d%d",&n,&d,&m);

        int u, v, c, p, e;

        for(int i = ; i < m; i++)

            fight[i].input();

        tot = ;

        for(int i = ; i <= n; i++){

            scanf("%d", &people[i] );

            tot += people[i];

        }

        int ans = solve();

        printf("Case #%d: ", Case );

        if( ans == - ) puts("Impossible");

        else printf("%d\n", ans );

    }

    return ;

}