我是每次spfa找最短路。
谁能解释下，为什么WA 谢谢。
小数据用的邻接矩阵。
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int map[500][500],cost[500][500];
bool hash[500];
int q[100000];
int n,ans;
int pre[500];
int dist[500];
void init()
{
freopen("s.in","r",stdin);
freopen("s.out","w",stdout);
}
void readdata()
{
scanf("%d\n",&n);
int i,x,y,j;
for(i=1; ; i++)
{
scanf("%d%d",&x,&y);
if(x==0 && y==0) break;
int tem;
scanf("%d%d\n",&map[x][y],&cost[x][y]);
cost[y][x]=-cost[x][y];
}
}
bool spfa()
{
int head,tail,i,x;
memset(hash,false,sizeof(hash));
for(i=1; i<=n; i++)
dist[i]=9999999;
head=0;
tail=1;
q[1]=1;
pre[1]=0;
dist[1]=0;
hash[1]=true;
do
{
head++;
x=q[head];
hash[x]=false;
for(i=1; i<=n; i++)
if(map[x][i]>0 && dist[i]>dist[x]+cost[x][i])
{
dist[i]=dist[x]+cost[x][i];
pre[i]=x;
if(hash[i]==false)
{
tail++;
q[tail]=i;
hash[i]=true;
}
}
}while(head<tail);
if(dist[n]<9999999) return true;
return false;
}
int min(int x,int y)
{
if(x<y) return x;
return y;
}
void deal()
{
int i,tem=999999;
for(i=n; i!=1; i=pre[i])
{
tem=min(tem,map[pre[i]][i]);
}
for(i=n; i!=1; i=pre[i])
{
map[pre[i]][i]-=tem;
map[i][pre[i]]+=tem;
ans+=cost[pre[i]][i]*tem;
}
}
void work()
{
ans=0;
while(spfa())
{
deal();
}
}
void print()
{
printf("%d\n",ans);
}
int main()
{
//init();
readdata();
work();
print();
return 0;
}
#include<stdio.h>
#include<cstring>
using namespace std;
int map[500][500],cost[500][500];
bool hash[500];
int q[100000];
int n,ans;
int pre[500];
int dist[500];
void init()
{
freopen("s.in","r",stdin);
freopen("s.out","w",stdout);
}
void readdata()
{
scanf("%d\n",&n);
int i,x,y,j;
for(i=1; ; i++)
{
scanf("%d%d",&x,&y);
if(x==0 && y==0) break;
int tem;
scanf("%d%d\n",&map[x][y],&cost[x][y]);
cost[y][x]=-cost[x][y];
}
}
bool spfa()
{
int head,tail,i,x;
memset(hash,false,sizeof(hash));
for(i=1; i<=n; i++)
dist[i]=9999999;
head=0;
tail=1;
q[1]=1;
pre[1]=0;
dist[1]=0;
hash[1]=true;
do
{
head++;
x=q[head];
hash[x]=false;
for(i=1; i<=n; i++)
if(map[x][i]>0 && dist[i]>dist[x]+cost[x][i])
{
dist[i]=dist[x]+cost[x][i];
pre[i]=x;
if(hash[i]==false)
{
tail++;
q[tail]=i;
hash[i]=true;
}
}
}while(head<tail);
if(dist[n]<9999999) return true;
return false;
}
int min(int x,int y)
{
if(x<y) return x;
return y;
}
void deal()
{
int i,tem=999999;
for(i=n; i!=1; i=pre[i])
{
tem=min(tem,map[pre[i]][i]);
}
for(i=n; i!=1; i=pre[i])
{
map[pre[i]][i]-=tem;
map[i][pre[i]]+=tem;
ans+=cost[pre[i]][i]*tem;
}
}
void work()
{
ans=0;
while(spfa())
{
deal();
}
}
void print()
{
printf("%d\n",ans.0);
}
int main()
{
//init();
readdata();
work();
print();
return 0;
}