把自己原來做過的幾道感覺不錯的圖論題貼過來。
[無向圖點(diǎn)雙][POJ2942]Knights of the Round Table
題目大意:有N個騎士,給出有兩兩之間有仇恨的關(guān)系,要求安排一種環(huán)形座次使得總?cè)藬?shù)為奇數(shù)而且其實之間不會發(fā)生沖突。
題解:首先根據(jù)給出的關(guān)系可以確定兩兩之間沒有仇恨的關(guān)系,然后根據(jù)該關(guān)系構(gòu)建圖。容易知道,最后安排的人必定在同一個點(diǎn)雙連通分量當(dāng)中(否則不會形成環(huán))。然后要在每個點(diǎn)雙當(dāng)中尋找一個奇圈。直接給出兩個霸氣的定理:1.如果一個點(diǎn)雙連通分量中存在奇圈,那么整個點(diǎn)雙連通分量的所有點(diǎn)必定也在一個奇圈中。
2.一個點(diǎn)雙連通分量如果不是二分圖則一定包含奇圈
1
#include <iostream>
2#include <cstdio>
3#include <algorithm>
4#include <vector>
5#include <stack>
6using namespace std;
7int N,M;
8bool discnt[1005][1005],Stay[1005];
9vector<int> adj[1005];
10int Color,Time,dfn[1005],low[1005],color[1005],bw[1005],Ans;
11stack< pair<int,int> > Stack;
12
13
bool isDiv(int u,int _bw)
{
14
bw[u]=_bw;
15 int i,node;
16
for(i=0;i<adj[u].size();i++){
17 node=adj[u][i];
18 if(color[node]==Color){
19 if(bw[node]==-1){
20 if(!isDiv(node,!_bw)) return false;
21
}
22 else if(bw[node]==_bw) return false;
23 }
24 }
25 return true;
26
}
27
28void dfs(int u,int fa){
29 int i,j,node;
30 dfn[u]=low[u]=++Time;
31 for(i=0;i<adj[u].size();i++){
32 node=adj[u][i];
33 if(!dfn[node]){
34 Stack.push(make_pair(u,node));
35 dfs(node,u);
36 low[u]=min(low[u],low[node]);
37 if(low[node]>=dfn[u]){
38 ++Color;
39 pair<int,int> edge_1=make_pair(node,u);
40 pair<int,int> edge_2=make_pair(u,node);
41 while(Stack.top()!=edge_1&&Stack.top()!=edge_2&&!Stack.empty()){
42 color[Stack.top().first]=color[Stack.top().second]=Color;
43 Stack.pop();
44 }
45 color[Stack.top().first]=color[Stack.top().second]=Color;
46 Stack.pop();
47 memset(bw,-1,sizeof(bw));
48 if(!isDiv(u,1)){
49 for(j=1;j<=N;j++){
50 if(color[j]==Color){
51 Stay[j]=true;
52 }
53 }
54 }
55 }
56 }
57 else if(node!=fa){
58
59 low[u]=min(low[u],dfn[node]);
60 }
61 }
62}
63
64
65int main(){
66
67 while(scanf("%d%d",&N,&M)!=EOF){
68 if(N+M==0) break;
69 int i,j,a,b;
70 for(i=1;i<=N;i++) adj[i].clear();
71 memset(discnt,false,sizeof(discnt));
72 for(i=1;i<=M;i++){
73 scanf("%d%d",&a,&b);
74 discnt[a][b]=discnt[b][a]=true;
75 }
76 for(i=1;i<=N;i++){
77 for(j=1;j<=N;j++){
78 if(i==j) continue;
79 if(!discnt[i][j]){
80 adj[i].push_back(j);
81 }
82 }
83 }
84 memset(dfn,0,sizeof(dfn));
85 memset(low,0,sizeof(low));
86
87 memset(Stay,0,sizeof(Stay));
88 memset(color,0,sizeof(color));
89 Stack=stack< pair<int,int> >();
90 Color=0;
91 for(i=1;i<=N;i++){
92 if(!dfn[i]){
93 Time=0;
94 dfs(i,0);
95 }
96 }
97 Ans=N;
98 for(i=1;i<=N;i++) if(Stay[i]) Ans--;
99 printf("%d\n",Ans);
100 }
101 return 0;
102}
校賽時的I題,Special Fish
困惑的地方:比賽時候我們想到KM,然后想起一句話,KM只能做完備匹配,于是沒有寫。后來發(fā)現(xiàn)大家都是直接一遍KM就過了,回來我寫成費(fèi)用流發(fā)現(xiàn)不行。答案不應(yīng)該是最后的cost而應(yīng)該是 Max(cost),然后被tclsm大牛質(zhì)疑了,于是有如下討論研究:
關(guān)鍵點(diǎn):這個圖不是完備匹配。
1)為什么KM可以直接做就AC了?KM做出來不是完備匹配么?NO！KM做出來還是完備匹配,不過對于非完備的用邊權(quán)為0的邊代替了。那么去掉這些邊權(quán)為0的邊可以么?答案是不可以,見下文
2)用費(fèi)用流做:
對于每個點(diǎn)i，我拆成了i和i'然后用了兩種方式建圖
1.s-> all i cost =0 cap=1
all i'->t cost =0 cap=1
所有i可以攻擊j的 i->j' cost=-（vali^valj） cap=1
做費(fèi)用流，wa掉，部分比答案小
2.s-> all i cost =0 cap=1
all i'->t cost =0 cap=1
所有i可以攻擊j的 i->j' cost=vali^valj cap=1
所有i不可以攻擊j的 i->j' cost=0 cap=1
做費(fèi)用流 AC
為什么會出現(xiàn)這種問題?由于我們做的是最小費(fèi)用最大流,所以前提條件是流量最大,之后費(fèi)用最小。于是這個題的關(guān)鍵點(diǎn)終于出來了--最小費(fèi)用的情況下是不是保證最大流?直觀的看貌似是的,因為如果最小費(fèi)用的情況不是最大流的話,那么由于費(fèi)用都是負(fù)數(shù),可以再找一條增廣路來減小費(fèi)用。直接看這個好像沒有什么問題,而且之前和zz討論他也以這個為論點(diǎn)。但是在說這句話的時候忘記了一個很重要的問題--后向邊!!!從后向邊走費(fèi)用一定是負(fù)數(shù)么?No!所以這么下來未必會減少費(fèi)用而最后cost也未必是答案。
改進(jìn)方法:1.使用模型2是的原圖可以達(dá)到最大流 2.取Max (cost)
感謝tclsm大牛的指點(diǎn),感謝好友zz的討論~
POJ 3177 邊雙連通分量
題目大意:給一個無向圖,求最少添加多少條邊可以使得任意兩個頂點(diǎn)間至少有兩條不相交的路徑。
題解:如果存在兩個頂點(diǎn),他們之間只有一條路徑或者所有路徑相交,那么必定有橋。所以對于原圖收縮邊雙連通分量,然后形成一棵樹,答案就是樹中(葉子節(jié)點(diǎn)個數(shù)+1)/2 (正確性:不會嚴(yán)格證明,畫個圖葉子之間兩兩連一下感覺沒問題...)
1#include <iostream>
2#include <vector>
3using namespace std;
4int t,f,r,dfn[5001],low[5001],bic[5001],color,indo[5001],ans;
5bool brige[5001][5001];
6vector<int> adj[5001];
7vector< pair<int,int> > Brige;
8
9void dfs(int u,int v){
10 dfn[u]=low[u]=++t;
11 int node;
12 for(int i=0;i<adj[u].size();i++){
13 node=adj[u][i];
14 if(!dfn[node]){
15 dfs(node,u);
16 low[u]=min(low[u],low[node]);
17 if(low[node]>dfn[u]){
18 brige[node][u]=brige[u][node]=true;
19 Brige.push_back(make_pair(u,node));
20 }
21 }
22 else if(node!=v){
23 low[u]=min(low[u],dfn[node]);
24 }
25 }
26}
27
28void floodfill(int u){
29 bic[u]=color;
30 int node;
31 for(int i=0;i<adj[u].size();i++){
32 node=adj[u][i];
33 if(!bic[node]&&!brige[u][node]){
34 floodfill(node);
35 }
36 }
37}
38
39
40int main(){
41 scanf("%d%d",&f,&r);
42 int i,j,a,b;
43 for(i=1;i<=r;i++){
44 scanf("%d%d",&a,&b);
45 adj[a].push_back(b);
46 adj[b].push_back(a);
47 }
48 dfs(1,0);
49 for(i=1;i<=f;i++){
50 if(!bic[i]){
51 ++color;
52 floodfill(i);
53 }
54 }
55 for(i=0;i<Brige.size();i++){
56 indo[bic[Brige[i].first]]++;
57 indo[bic[Brige[i].second]]++;
58 }
59 for(i=1;i<=color;i++){
60 if(indo[i]==1) ans++;
61 }
62 printf("%d\n",(ans+1)/2);
63 return 0;
64}
posted on 2010-08-01 19:55
OpenWings 閱讀(353)
評論(0) 編輯 收藏 引用