1) Bellman Ford算法找負環(huán)的應用.
#include?<cstdio>
#include?<cstdlib>
#include?<queue>
#include?<deque>
using?namespace?std;
struct?Node?
{
????int?to;
????int?weight;
????Node?*next;
};
#define?MAXFIELD?(1000?+?10)
#define?MAXPATH?(2500?+?10)
#define?MAXWORMHOLE?(200?+?10)
Node?nodeHead[MAXFIELD];
Node?nodes[MAXPATH?*?2?+?MAXWORMHOLE];
int?dis[MAXFIELD?+?1];
bool?isInQueue[MAXFIELD?+?1];
int?allocPos?=?0;
Node?*getNode()?{
????return?nodes?+?allocPos++;
}
void?initGraph(int?n)?{
????allocPos?=?0;
????int?i?=?0;
????for?(i?=?0;?i?<?n;?++i)?{
????????nodeHead[i].next?=?NULL;
????????dis[i]?=?0;
????}
}
void?addEdge(int?from,?int?to,?int?timeNeed)?{
????Node?*newNode?=?getNode();
????newNode->next?=?nodeHead[from].next;
????newNode->to?=?to;
????newNode->weight?=?timeNeed;
????nodeHead[from].next?=?newNode;
}
int?main()?{
????int?caseCount,?fieldCount,?pathCount,?wormHoleCount;
????int?i,?j,?from,?to,?timeNeed;
????scanf("%d",?&caseCount);
????for?(i?=?0;?i?<?caseCount;?i++)?{
????????scanf("%d%d%d",?&fieldCount,?&pathCount,?&wormHoleCount);
????????initGraph(fieldCount?+?1);
????????for?(j?=?0;?j?<?pathCount;?j++)?{
????????????scanf("%d%d%d",?&from,?&to,?&timeNeed);
????????????addEdge(from,?to,?timeNeed);
????????????addEdge(to,?from,?timeNeed);
????????}
????????for?(j?=?0;?j?<?wormHoleCount;?++j)?{
????????????scanf("%d%d%d",?&from,?&to,?&timeNeed);
????????????addEdge(from,?to,?-timeNeed);
????????}
????????//?關鍵:?按照題目的要求,?可以看出是找圖中有沒有負環(huán)
????????//?引入一個超級點s,?s能夠到達任意一個field,?但是沒有任何field能夠到達s
????????//?然后如果圖中不存在負環(huán),?則在經(jīng)過fieldCount次松弛(我叫優(yōu)化)以后,?
????????//?就沒有辦法使任意一個field節(jié)點的權(quán)值變小了,?而如果存在負環(huán),?
????????//?則還能松弛/優(yōu)化.
????????//?這就是為什么初始化時需要把所有的field都壓入隊列.
????????deque<int>?q;
????????for?(j?=?1;?j?<=?fieldCount;?++j)?{
????????????q.push_back(j);
????????????isInQueue[j]?=?true;
????????}
????????bool?answer?=?false;
????????int?round?=?0;
????????while?(!q.empty())?{
????????????int?n?=?q.size();
????????????for?(j?=?0;?j?<?n;?j++)?{
????????????????int?u?=?q.front();
????????????????q.pop_front();
????????????????isInQueue[u]?=?false;
????????????????Node?*tra;
????????????????for?(tra?=?nodeHead[u].next;?tra?!=?NULL;?tra?=?tra->next)?{
????????????????????int?temp?=?tra->weight?+?dis[u];
????????????????????if?(temp?<?dis[tra->to])?{
????????????????????????dis[tra->to]?=?temp;
????????????????????????if?(!isInQueue[tra->to])?{
????????????????????????????q.push_back(tra->to);
????????????????????????????isInQueue[tra->to]?=?true;
????????????????????????}
????????????????????}
????????????????}
????????????}
????????????round++;
????????????if?(round?>?fieldCount)?{
????????????????answer?=?true;
????????????????q.clear();
????????????????break;
????????????}
????????}
????????if?(answer)?{
????????????puts("YES");
????????}
????????else?{
????????????puts("NO");
????????}
????}
????return?0;
}