#include <iostream>
#include <cstdio>

using namespace std;

int n, C, M, K;
int dist[235][235];
const int inf = 1000000009;


#define MAXN 235
#define MAXE 12500
#define inf 0x3f3f3f3f
struct Edge{ int v,c,x; }E[MAXE]; //指向的节点, 剩余可增⼲⼴广的流量 int l[MAXN],e; //必须保证e的初始值是偶数 void init(){ e=0; memset(l,-1,sizeof(l)); }

int l[MAXN],e; //必须保证e的初始值是偶数

void init(){ e=0; memset(l,-1,sizeof(l)); }

inline void insert(int u,int v,int f,int invf){ //u->v=f
    E[e].v=v; E[e].c=f;   E[e].x=l[u]; l[u]=e++;
    E[e].v=u; E[e].c=invf;E[e].x=l[v]; l[v]=e++;
}

struct Netflow{
    int src,sink; //需要初始化
    //以上
    int L[MAXN],Q[MAXN]; //L=level Q=queue
    int _bfs(){ //广搜,并标记level(只取流量⼤大于0的边)
        int s=0,t=0,u;
        memset(L,0xff,sizeof(L));
        L[src]=0; Q[t++]=src;
        while (s<t){
            u=Q[s++];
            for (int p=l[u];p>=0;p=E[p].x)
                if (E[p].c && L[E[p].v]==-1)
                    L[(Q[t++]=E[p].v)]=L[u]+1;
        }
        return L[sink]!=-1;
    }
    int _find(int u,int in){ //in:能流⼊入u节点的最⼤大流量. 返回u节点能流出的最⼤大流量 if (u==sink) return in;
        int t,w=0; //w表⽰示已经从u流出的总流量
        for (int p=l[u];p>=0 && w<in;p=E[p].x){
            if (E[p].c>0 && L[E[p].v]==L[u]+1){
                if (t=_find(E[p].v,min(E[p].c,in-w))){
                    E[ p].c-=t;
                    E[p^1].c+=t; //这⾥里表⽰示必须 w+=t; //多路增⼲⼴广优势巨⼤大
                }
            }
        }
        if( w<in )L[u]=-1;//关键的⼀一句话
        return w;
    }
    int dinic(){
        int t,res=0;
        while (_bfs()) {
            while (t=_find(src,inf))res+=t;
        }
        return res;
    }
}flow; //********模板结束***********
//init(); insert(...); flow.src=.. ; flow.sink; flow.dinic();


bool check(int max_dist) {
    init();
    //1-K machines, K+1 - K+C, cows, C+K+1 source, C+K+2 sink
    for (int i = 0; i < K; ++i) {
        for (int j = K; j < K + C; ++j) {
            //j cows, i machines
            if (dist[i][j] <= max_dist) {
                insert(j + 1, i + 1, inf, 0);
            }
        }
    }
    flow.src = K + C + 1;
    flow.sink = K + C + 2;
    for (int i = 1; i <= K; ++i) {
        insert(i, flow.sink, M, 0);
    }
    for (int i = K + 1; i <= K + C; ++i) {
        insert(flow.src, i, 1, 0);
    }
    int max_flow = flow.dinic();
    if (max_flow == C) {
        return true;
    }
    return false;
}



int main() {
    while (scanf("%d%d%d", &K, &C, &M) != EOF) {
        for (int i = 0; i < K + C; ++i) {
            for (int j = 0; j < K + C; ++j) {
                scanf("%d", &dist[i][j]);
                if (dist[i][j] == 0) dist[i][j] = inf;
                if (i == j) dist[i][j] = 0;
            }
        }
        for (int k = 0; k < K + C; ++k) {
            for (int i = 0; i < K + C; ++k) {
                if (k == i) continue;
                for (int j = 0; j < K + C; ++j) {
                    if (i == j || k == j) continue;
                    if (dist[i][k] + dist[k][j] <= dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        int L = 0, R = inf;
        while (L < R) {
            int mid = L + (R - L) / 2;
            bool flag = check(mid);
            if (flag) {
                R = mid;
            } else {
                L = mid;
            }
        }
        int max_distance = L;
        printf("%d\n", max_distance);
        
    }
    return 0;
}

• Re:为什么RE (7) lolxu 2016-07-26 15:44:55