1927: [Sdoi2010]星際競速
Time Limit: 20 Sec? Memory Limit: 259 MBSubmit: 2556? Solved: 1580
[Submit][Status][Discuss]
Description
10年一度的銀河系賽車大賽又要開始了。作為全銀河最盛大的活動之一，奪得這個項目的冠軍無疑是很多人的
夢想，來自杰森座α星的悠悠也是其中之一。賽車大賽的賽場由N顆行星和M條雙向星際航路構成，其中每顆行星都
有一個不同的引力值。大賽要求車手們從一顆與這N顆行星之間沒有任何航路的天體出發，訪問這N顆行星每顆恰好
一次，首先完成這一目標的人獲得勝利。由于賽制非常開放，很多人駕駛著千奇百怪的自制賽車來參賽。這次悠悠
駕駛的賽車名為超能電驢，這是一部凝聚了全銀河最尖端科技結晶的夢幻賽車。作為最高科技的產物，超能電驢有
兩種移動模式：高速航行模式和能力爆發模式。在高速航行模式下，超能電驢會展開反物質引擎，以數倍于光速的
速度沿星際航路高速航行。在能力爆發模式下，超能電驢脫離時空的束縛，使用超能力進行空間跳躍——在經過一
段時間的定位之后，它能瞬間移動到任意一個行星。天不遂人愿，在比賽的前一天，超能電驢在一場離子風暴中不
幸受損，機能出現了一些障礙：在使用高速航行模式的時候，只能由每個星球飛往引力比它大的星球，否則賽車就
會發生爆炸。盡管心愛的賽車出了問題，但是悠悠仍然堅信自己可以取得勝利。他找到了全銀河最聰明的賢者——
你，請你為他安排一條比賽的方案，使得他能夠用最少的時間完成比賽。
Input
第一行是兩個正整數N,M。第二行N個數A1~AN，其中Ai表示使用能力爆發模式到達行星i所需的定位時間。接下
來M行，每行3個正整數ui,vi,wi，表示在編號為ui和vi的行星之間存在一條需要航行wi時間的星際航路。輸入數據
已經按引力值排序，也就是編號小的行星引力值一定小，且不會有兩顆行星引力值相同。
Output
僅包含一個正整數，表示完成比賽所需的最少時間。
Sample Input
3 3
1 100 100
2 1 10
1 3 1
2 3 1
Sample Output
12
HINT
說明：先使用能力爆發模式到行星1，花費時間1。然后切換到高速航行模式，航行到行星2，花費時間10。之
后繼續航行到行星3完成比賽，花費時間1。雖然看起來從行星1到行星3再到行星2更優，但我們卻不能那樣做，因
為那會導致超能電驢爆炸。N≤800，M≤15000。輸入數據中的任何數都不會超過106。輸入數據保證任意兩顆行星
之間至多存在一條航道，且不會存在某顆行星到自己的航道。
?
感覺這個題挺神奇的。涉及到一些巧妙的轉換。
一看見每個點恰好去一次，首先想到的就是拆點，每個入點向出點連容量1的邊，但這個題有有點不一樣，而這就是此題神秘的地方。
?
此題的困難之處：如何選擇出發點。
想了很久都沒有想到該怎么解決出發點的問題，翻了翻題解，發現它避開了這個問題，將其轉化成了另一種思路。
?
先說建邊
每個點i拆成xi，yi
S向xi連容量為1費用0的邊，S向yi連容量1費用ti的邊
yi向T連容量1費用0的邊
對于每條給定的邊u->v?? w， xu->yv連容量1費用w的邊
?
那么這具體表示什么意思呢？
xi表示到達這個點后的狀態，應該考慮怎么走。yi表示剛到這個點，完成每個點走一次的任務。
yi向T連邊是常規操作。
xu->yv是因為到達u點完成任務后，可以考慮走向下一個地方。
S->xi是因為每次在yi完成任務后我們不會到xi去，轉化成S向xi走費用0，并從xi到達其他地方。
S->yi是因為從其他星球跳躍到yi可以轉化成從S直接跳到yi，不用考慮起跳點是哪個星球。
?
以上建邊有一個共性：只考慮結果，不考慮過程
把復雜的過程轉化成了簡單的過程，結果相同
?
?
再說一次，這個題目是非常有意思的。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #define inf 0x3f3f3f3f #define ll long long #define N 1605 using namespace std; int n,m,tot,S,T,hd[N],a[N],d[N],cur[N],vis[N],pre[N]; struct edge{int u,v,next,w,cap;}e[N*50]; void adde(int u,int v,int w,int c){e[tot].v=v;e[tot].u=u;e[tot].next=hd[u];e[tot].cap=c;e[tot].w=w;hd[u]=tot++; }bool spfa(int &flow,int &cost){queue<int>q;memset(pre,-1,sizeof(pre));memset(d,0x3f,sizeof(d));a[S]=inf;d[S]=0;q.push(S);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=hd[u];~i;i=e[i].next){int v=e[i].v;if(e[i].cap&&d[v]>d[u]+e[i].w){d[v]=d[u]+e[i].w;pre[v]=i;a[v]=min(a[u],e[i].cap);if(vis[v])continue;vis[v]=1;q.push(v);}}}if(d[T]==inf)return 0;flow+=a[T];cost+=a[T]*d[T];int u=T;while(u!=S){e[pre[u]].cap-=a[T];e[pre[u]^1].cap+=a[T];u=e[pre[u]].u;}return 1; } int main(){ #ifdef wsyfreopen("data.in","r",stdin); #else//freopen(".in","r",stdin);//freopen(".out","w",stdout); #endifmemset(hd,-1,sizeof(hd));scanf("%d%d",&n,&m);S=0;T=n*2+1;for(int i=1;i<=n;i++){int t;scanf("%d",&t);adde(S,i,0,1);adde(i,S,0,0);adde(S,i+n,t,1);adde(i+n,S,-t,0);adde(i+n,T,0,1);adde(T,i+n,0,0);}for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(a>b)swap(a,b);adde(a,b+n,c,1);adde(b+n,a,-c,0);}int flow=0,cost=0;while(spfa(flow,cost));printf("%d",cost);return 0; }
)
)
