POJ-3259 解题报告

题意简述

农夫共有F(1≤F≤5)个农场,每个农场有N块田(1 ≤ N ≤ 500)和M条普通无向路(1 ≤ M ≤ 2500),走过这些路需要一定时间。同时还存在W条有向虫洞(1 ≤ W ≤ 200),走这些虫洞可倒流一定时间。问对于各个农场,农夫是否有可能从某点出发,回到原点时时间早于出发时间。每个农场输出一行。可能则输出YES,否则为NO。

算法分析

这题可抽象为:对于F张图,每张图有M条权值为正的无向路和W条权值为负的有向路。问图中是否存在负权环。

处理时将无向路处理为两条有向路。

因为涉及负权,所以使用Bellman-Ford判断负权环即可。在处理过程中,为了避免非连通图造成的漏解,新建一个与所有节点都联通的节点并将它作为Bellman-Ford的起点。

关于Bellman-Ford和其余最短路算法,以后单独开一篇日志讨论~

Problem Status: AC。时间47ms,内存232k

程序样例

[c]#include<stdio.h>

int bellman_ford(int n, int edge, int e[][3])
{
int d[1001],i,j,flag;
d[0]=0;
for(i=1;i<=n;i++)
d[i]=10000000;
for(i=1;i<n;i++)
{
flag=0;
for(j=0;j<edge;j++)
if (d[e[j][1]]>d[e[j][0]]+e[j][2])
{
d[e[j][1]]=d[e[j][0]]+e[j][2];
flag=1;
}
if(!flag) break;
}
for(j=0;j<edge;j++)
if (d[e[j][1]]>d[e[j][0]]+e[j][2])
return 1;
return 0;
}

int main()
{
int t,n,m,w,e[6000][3],i,edge;
scanf("%d",&t);
while(t>0)
{
edge=0;
scanf("%d%d%d",&n,&m,&w);
for(i=1;i<=n;i++)
{
e[edge][0]=0;
e[edge][1]=i;
e[edge][2]=0;
edge++;
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&e[edge][0],&e[edge][1],&e[edge][2]);
edge++;
e[edge][0]=e[edge-1][1];
e[edge][1]=e[edge-1][0];
e[edge][2]=e[edge-1][2];
edge++;
}
for(i=0;i<w;i++)
{
scanf("%d%d%d",&e[edge][0],&e[edge][1],&e[edge][2]);
e[edge][2]=-e[edge][2];
edge++;
}

if(bellman_ford(n,edge,e)) printf("YESn");
else printf("NOn");

t–;
}
}
[/c]

Leave a Reply

Your email address will not be published. Required fields are marked *