#include <iostream>
#include <queue>
using namespace std;
typedef struct edgenode
{
    long e;
    struct edgenode *next;
}Edge;
Edge edge[203];
long r[203][203],f[203][203];
long path[210];
char flag[210];
long m;
long BFS(long s)                //广搜增广路
{
    Edge *te;
    queue<long> q;
    long tq1;
    memset(flag,0,sizeof(flag));
    q.push(s);
    flag[s]=1;
    while(!q.empty())
    {
        tq1=q.front(),q.pop();
        te=edge[tq1].next;
        while(te!=NULL)
        {
            if(flag[te->e]==0&&r[tq1][te->e]<f[tq1][te->e])        //结点未被访问过且还可有流通过
            {
                path[te->e]=tq1;            //记录路径
                flag[te->e]=1;        
                if(te->e==m)
                return 1;            //找到增广路返回1
                q.push(te->e);
            }
            te=te->next;
        }
    }
    return -1;            //未找到返回-1
}
int main()
{
    long n,i,s,e,c,sum1,min1,temp1;
    Edge *te;
    //freopen("in.txt","r",stdin);
    while(scanf("%ld%ld",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%ld%ld%ld",&s,&e,&c);    
            f[s][e]+=c;                //构造网络
            te=new Edge;        
            te->e=e;                    //插入链表
            te->next=edge[s].next;                //初值为NULL,注意释放空间
            edge[s].next=te;
        }
        while(1)
        {
            if(BFS(1)==-1)
            break;
            i=m;
            min1=0x7FFFFFFF;
            while(1)
            {
                temp1=f[path[i]][i]-r[path[i]][i];        //最小值
                if(min1>temp1)
                min1=temp1;
                i=path[i];
                if(i==1)
                break;
            }
            i=m;
            while(1)
            {                            //构造残留网络
                r[path[i]][i]+=min1;
                r[i][path[i]]=-r[path[i]][i];
                i=path[i];
                if(i==1)
                break;
            }
        }
        for(i=1,sum1=0;i<m;i++)
           sum1+=r[i][m];
        printf("%ld\n",sum1);
        memset(f,0,sizeof(f));
        memset(r,0,sizeof(r));
        memset(edge,0,sizeof(edge));
    }
    return 0;
} 

• Re:在HDU过了，在PKU却过不了，PKU有什么HDU没测的数据吗？高手指教一下！！！谢谢！ (2448) Me_Fly 2010-10-01 17:20:57