这是我的代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
#define IN64 (__int64)1 << 60
#define N 300
int F,P;
int farm[N][N],pre[N],mincow[N],flow[N][N];
__int64 cost[N][N],mincost,sum;

int min(int a, int b)
{
    return a < b ? a : b;
}

void input()
{
    int i,j;
    int a,b,c;
    scanf("%d%d",&F,&P);
    memset(farm,0,sizeof(farm));
    for(i = 1; i <= F; i++)
    {
        scanf("%d%d",&a,&b);
        farm[0][i] = a;
        farm[i][F+1] = b;
    }
    for(i = 1; i <= F; i++)
    {
        for(j = 1; j <= F; j++)
            cost[i][j] = IN64;
        cost[i][i] = 0;
    }
    for(i = 1; i <= P; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(c < cost[a][b]) cost[a][b] = cost[b][a] = c;
    }
}

void floyd(int n)
{
    int i,j,k;
    for(k = 1; k <= n;k++)
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                if(cost[i][k] != INF && cost[k][j] != INF && cost[i][k]+cost[k][j] < cost[i][j])
                    cost[i][j] = cost[i][k]+cost[k][j];

}

void build_graph()
{
    int i,j;
    for(i = 1; i <= F; i++)
        for(j = 1; j <= F; j++)
            if(cost[i][j] != IN64)
                farm[i][j] = INF;
}

bool SPFA()
{
    int i,j,tmp;
    __int64 dist[N];
    bool sign[N];
    queue<int> que;
    while(!que.empty()) que.pop();
    for(i = 1; i <= F+1; i++) dist[i] = IN64;
    memset(sign,0,sizeof(sign));
    for(i = 0; i <= F+1; i++) {pre[i] = -1;mincow[i] = INF;}
    dist[0] = 0;
    que.push(0); sign[0] = true;
    while(!que.empty())
    {
        tmp = que.front(); que.pop(); sign[tmp] = false;
        for(i = 1; i <= F+1;i++)
            if( ((j = farm[tmp][i]-flow[tmp][i])>0) && dist[tmp]+cost[tmp][i] < dist[i])
            {
                dist[i] = dist[tmp] + cost[tmp][i];
                pre[i] = tmp;
                mincow[i] = min(mincow[tmp],j);
                if(!sign[i]) {que.push(i); sign[i] = true;}
            }
    }
    if(mincow[F+1] != INF) return true;
    else return false;
}

void mincost_maxflow()
{
    int i,j;
    int u,v;
    bool flag = false;
    memset(flow,0,sizeof(flow));
    mincost = 0;
    while(SPFA())
    {
        for(u = F+1; u != 0; u = v)
        {
            v = pre[u];
            flow[v][u] += mincow[F+1];
            flow[u][v] -= mincow[F+1];
        }
    }
    for(i = 1; i <= F; i++)
        if(farm[0][i] != flow[0][i]){flag = true; break;}
    if(flag) printf("-1\n");
    else
    {
        for(i = 1; i <= F; i++)
            for(j = 1; j <= F; j++)
                if(flow[i][j] > 0 && cost[i][j] > mincost)
                    mincost = cost[i][j];
        printf("%I64d\n",mincost);
    }
}

int main()
{
    int i,j;
    input();
    floyd(F);
    build_graph();
    mincost_maxflow();
    return 0;
}

• Re:求最小费最大流WA的数据 (302) carber 2010-05-06 19:33:20