題面

這道題太神了吧,從昨晚七點半做到今天下午兩點.

我經(jīng)歷了以下折騰(以下內(nèi)容可跳過):

• 一開始想的是用Tarjan縮點,然后以可以被收買的間諜為起點跑最短路,通過路徑染色,讓一條路徑上的點的權(quán)值等于起點(也就是可以被收買的美國間諜的編號),然后枚舉每一個點,用它對應(yīng)的路徑,累加權(quán)值得到答案,如果有點的權(quán)值為正無窮,那么就說明有間諜無法收買,再掃一遍染色數(shù)組找出編號最小的點輸出NO.

這種方式貌似可以,但是在跑最短路的時候,松弛操作會把權(quán)值更小的路徑更新進來,但是這條最短路可能是無法確保跑向權(quán)值更大的點的前綴點的,所以說會導(dǎo)致權(quán)值反而更大.這種方法最高得了52分.

比如下面這張圖:

1,2,3,4號點明顯是個強聯(lián)通分量,收買這個分量的代價為10.

5號點也是一個強連通分量,收買它的代價為20.

該圖只有從5號點開始,才可以遍歷完所有的點,總代價為20.

但是在跑最短路時,進入縮過點后的1,2,3,4節(jié)點后,會把這個點的權(quán)值松弛為10,但是這個10是無法跑完整個圖的,這也導(dǎo)致總代價變?yōu)榱?0;

• 然后我甚至想縮點之后跑一邊最小生成樹,但是算了下這樣做會超時.

• 之后我又想好了好久,和zxs大佬在中午恰飯的時候交流了下這道題,才想出來可以記錄下所有入度為0的點,然后累加這些點的權(quán)值.這是因為入度為0的點是一定要被收買的,不然就無法遍歷完全圖,如果有間諜點無法被收買而且無法被其他間諜告發(fā),就輸出NO.

還有一些細節(jié)在代碼里解釋罷,各位在閱讀我的變量名時只用看下劃線后的部分.

代碼:

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue>using namespace std;stack<int>s;struct edge {int to,next; }e[10010];int OddToThePeoplesVolunteerArmy_n,GreatSoviet_p,TheSovietUnion_CntSize,PeoplesRupublic_TimeCnt,YpaForOurGreatMotherland_r,TheDefenderOfMoscow_size,TheInternationalMustCometrue_ans; int head[10010],dfn[10010],low[10010],indu[10010],dis[10010],color[10010],Nodedis[10010]; bool flag[10010];void EdgeAdd(int,int); void Tarjan(int);int main() {memset(head,-1,sizeof(head));memset(Nodedis,0x3f,sizeof(Nodedis));memset(dis,0x3f,sizeof(dis));scanf("%d%d",&OddToThePeoplesVolunteerArmy_n,&GreatSoviet_p);for(int _=1;_<=GreatSoviet_p;_++){int id,USAIsRubbish;scanf("%d%d",&id,&USAIsRubbish);dis[id]=USAIsRubbish;}scanf("%d",&YpaForOurGreatMotherland_r);for(int _=1;_<=YpaForOurGreatMotherland_r;_++){int father,son;scanf("%d%d",&father,&son);EdgeAdd(father,son);}for(int _=1;_<=OddToThePeoplesVolunteerArmy_n;_++){if(dfn[_]==0&&dis[_]!=0x3f3f3f3f)//把可以收買的美國間諜進入Tarjan縮點,這樣縮出來的點才能夠被遍歷.{Tarjan(_);}}for(int _=1;_<=OddToThePeoplesVolunteerArmy_n;_++)//縮完點后如果存在無法被收買,又無法被其它間諜指控的點,就說明無法收買所有間諜.{if(dfn[_]==0){printf("NO\n%d\n",_);return 0;}}for(int _=1;_<=OddToThePeoplesVolunteerArmy_n;_++){for(int __=head[_];__!=-1;__=e[__].next){int to=e[__].to;if(color[_]!=color[to]){indu[color[to]]++;//統(tǒng)計入度.}}}for(int _=1;_<=TheSovietUnion_CntSize;_++){if(indu[_]==0)//累加必須收買的間諜的代價.{TheInternationalMustCometrue_ans+=Nodedis[_]; // printf("Nodedis:%d\n",Nodedis[_]);}}printf("YES\n%d\n",TheInternationalMustCometrue_ans); return 0; }void EdgeAdd(int from,int to) {e[++TheDefenderOfMoscow_size].to=to;e[TheDefenderOfMoscow_size].next=head[from];head[from]=TheDefenderOfMoscow_size; }void Tarjan(int FuckTrump_from) {dfn[FuckTrump_from]=low[FuckTrump_from]=++PeoplesRupublic_TimeCnt;s.push(FuckTrump_from);flag[FuckTrump_from]=true;for(int _=head[FuckTrump_from];_!=-1;_=e[_].next){int to=e[_].to;if(dfn[to]==0){Tarjan(to);low[FuckTrump_from]=min(low[FuckTrump_from],low[to]);}else if(flag[to]==true){low[FuckTrump_from]=min(low[FuckTrump_from],dfn[to]);}}if(dfn[FuckTrump_from]==low[FuckTrump_from]){TheSovietUnion_CntSize++;while(!s.empty()){int RedAmryIsTheStrongest_temp=s.top();s.pop();flag[RedAmryIsTheStrongest_temp]=false;color[RedAmryIsTheStrongest_temp]=TheSovietUnion_CntSize;Nodedis[TheSovietUnion_CntSize]=min(Nodedis[TheSovietUnion_CntSize],dis[RedAmryIsTheStrongest_temp]);//縮點后的點的代價為原來的環(huán)的代價中最小的那個代價.color[RedAmryIsTheStrongest_temp]=TheSovietUnion_CntSize;//染色.if(RedAmryIsTheStrongest_temp==FuckTrump_from)break;}} }

轉(zhuǎn)載于:https://www.cnblogs.com/Lemir3/p/11097721.html

總結(jié)

以上是生活随笔為你收集整理的P1262_美帝的间谍网络被我部捕获!的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。