求教hdu2448,看到哪位大牛能找到代码错误之处
#include<stdio.h>
#include<string.h>
#include<queue>
#define inf 0x3f3f3f3f
#define maxn 1000+10
#define maxe 400000+10
using namespace std;
typedef struct Edge{
int from,to,c,w,next;
}Edge;
Edge edge[maxe];
int head[maxn];
int s,t,n,m,k,p,cnt;
int dist[maxn],pre[maxn];
bool in[maxn];
int min(int a,int b)
{
return a<b?a:b;
}
void add(int u,int v,int c,int w)
{
edge[cnt].from=u;edge[cnt].to=v;edge[cnt].c=c;edge[cnt].w=w;
edge[cnt].next=head[u];head[u]=cnt++;
edge[cnt].from=v;edge[cnt].to=u;edge[cnt].c=0;edge[cnt].w=-w;
edge[cnt].next=head[v];head[v]=cnt++;
return;
}
int spfa()
{
int i;
queue<int> q;
memset(in,0,sizeof(in));
memset(pre,-1,sizeof(pre));
for(i=0;i<=t;i++) dist[i]=inf;
in[s]=1;
dist[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
in[u]=0;
for(i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to,c=edge[i].c,w=edge[i].w;
if(c && dist[u]+w<dist[v])
{
dist[v]=dist[u]+w;pre[v]=i;
if(!in[v])
{
in[v]=1;
q.push(v);
}
}
}
}
if(dist[t]==inf) return 0;
int p,delta=inf;
p=t;
while(p!=s)
{
i=pre[p];
delta=min(delta,edge[i].c);
p=edge[i].from;
}
p=t;
while(p!=s)
{
i=pre[p];
edge[i].c-=delta;edge[i^1].c+=delta;
p=edge[i].from;
}
return delta*dist[t];
}
int mfmc()
{
int ans=0;
while(int delta=spfa()) ans+=delta;
return ans;
}
int main()
{
int i,j;
while(scanf("%d%d%d%d",&n,&m,&k,&p)!=EOF)
{
cnt=0;
memset(head,-1,sizeof(head));
s=0;t=m+n+1;
for(i=1;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
add(s,tmp,1,0);
}
for(i=1;i<=k;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
add(a,b,inf,w);add(b,a,inf,w);
}
for(i=1;i<=p;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
add(b,m+a,inf,w);
}
for(i=1;i<=n;i++)
add(m+i,t,1,0);
printf("%d\n",mfmc());
}
return 0;
}
和hdoj测试数据对比一下,发现有几组数据输出错误答案0.。但是不知道错哪了,望大牛指点 数据结构
[解决办法]
嗯我理解错了……你的代码可以处理一个station多个vessel的情况。我明天再看一下代码