把自己原來做過的幾道感覺不錯的圖論題貼過來。
[無向圖點雙][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)建圖。容易知道,最后安排的人必定在同一個點雙連通分量當中(否則不會形成環(huán))。然后要在每個點雙當中尋找一個奇圈。直接給出兩個霸氣的定理:1.如果一個點雙連通分量中存在奇圈,那么整個點雙連通分量的所有點必定也在一個奇圈中。
2.一個點雙連通分量如果不是二分圖則一定包含奇圈
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ā)現(xiàn)不行。答案不應(yīng)該是最后的cost而應(yīng)該是 Max(cost),然后被tclsm大牛質(zhì)疑了,于是有如下討論研究:
關(guān)鍵點:這個圖不是完備匹配。
1)為什么KM可以直接做就AC了?KM做出來不是完備匹配么?NO！KM做出來還是完備匹配,不過對于非完備的用邊權(quán)為0的邊代替了。那么去掉這些邊權(quán)為0的邊可以么?答案是不可以,見下文
2)用費用流做:
對于每個點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
做費用流，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
做費用流 AC
為什么會出現(xiàn)這種問題?由于我們做的是最小費用最大流,所以前提條件是流量最大,之后費用最小。于是這個題的關(guān)鍵點終于出來了--最小費用的情況下是不是保證最大流?直觀的看貌似是的,因為如果最小費用的情況不是最大流的話,那么由于費用都是負數(shù),可以再找一條增廣路來減小費用。直接看這個好像沒有什么問題,而且之前和zz討論他也以這個為論點。但是在說這句話的時候忘記了一個很重要的問題--后向邊!!!從后向邊走費用一定是負數(shù)么?No!所以這么下來未必會減少費用而最后cost也未必是答案。
改進方法:1.使用模型2是的原圖可以達到最大流 2.取Max (cost)
感謝tclsm大牛的指點,感謝好友zz的討論~
POJ 3177 邊雙連通分量
題目大意:給一個無向圖,求最少添加多少條邊可以使得任意兩個頂點間至少有兩條不相交的路徑。
題解:如果存在兩個頂點,他們之間只有一條路徑或者所有路徑相交,那么必定有橋。所以對于原圖收縮邊雙連通分量,然后形成一棵樹,答案就是樹中(葉子節(jié)點個數(shù)+1)/2 (正確性:不會嚴格證明,畫個圖葉子之間兩兩連一下感覺沒問題...)
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 閱讀(335)
評論(0) 編輯 收藏 引用