Question

poj1273 提交wrong answer 。求大神帮忙看下，代码如下： 题目链接http://poj.org/problem?id=1273

这题是求最大流的，我前面测试数据可以过，但就是wr,求c++代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<string.h>
using namespace std;
#define MAXN 250
#define MAX_VALUE 10000000
int a[MAXN][MAXN];
int path[MAXN];
int flow[MAXN][MAXN];
int value[MAXN];
int Ford_Fulkerson(int s,int t,int m)
{
int ans=0,k,j;
queue<int> que;
while(true)
{
memset(value,0,sizeof(value));
value[s]=MAX_VALUE;
que.push(s);
while(!que.empty())
{
int po=que.front();
que.pop();
for(k=1;k<=m;k++)
{
if(value[k]==0&&a[po][k]>flow[po][k])
{
path[k]=po;
que.push(k);
int temp=a[po][k]-flow[po][k];
value[k] = value[po] > temp ? temp : value[po];
}
}
}
if (value[t] == 0)
break;
for (j = t; j != s; j = path[j]) {
flow[path[j]][j] += value[t];
flow[j][path[j]] -= value[t];
}
ans += value[t];
}
return ans;
}
void init(int m)
{
int i,j,k;
for(k=0;k<m;k++)
path[k]=0;
for(i=0;i<=m;i++)
for(j=0;j<=m;j++)
{
flow[i][j]=0;
a[i][j]=0;
}
}
int main()
{
int n,m,i,j,w,k;

while(scanf("%d%d",&n,&m)!=EOF)
{
init(m);
for(k=0;k<n;k++)
{
scanf("%d%d%d",&i,&j,&w);
a[i][j]=w;
}

printf("%d\n",Ford_Fulkerson(1,m,m));
}
}

Answer 1

因为自己常常用的是dinic算法啊...表示比较难改你的程序...

  scanf("%d%d%d",&i,&j,&w);
             a[i][j]=w;

但是这个...你似乎是没有考虑重边的情况的....

改成a[i][j]+=w，然后我交了一次...

就AC啦...