當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

靠二进制画几何[图论]

發布時間：2025/4/16 编程问答 19 豆豆

生活随笔收集整理的這篇文章主要介紹了靠二进制画几何[图论] 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

@Kaike

今天來淺談一下圖，聽說自己寫總結的人grade++，rp++。

像我這樣可愛的人怎么能錯過這個機會呢嚶嚶嚶。

畢竟圖至少啃了15day++。

恩曾經的小弱渣從來都是仰望高端玩家虐圖論

聽說noip上一年考兩道大圖(つд?)而小弱渣還沒學到

嚇得本寶寶虎軀一震！！

恩廢話不多說，來開正文。

2019/01/27：

時隔兩年重新看這篇博客，又更新的好多東西，希望自己一直能不斷進步把，而不是一直啃以前的東西QAQ

-------------------我是萌噠噠的分割線--------------------

剛開始先學圖的儲存。

鄰接矩陣

鄰接矩陣就是跟二維數組長得一毛（mu）一樣奇奇怪怪的東xi

1 #include<iostream> 2 using namespace std; 3 int n,a[100][100]; 4 int main() 5 { 6 cin>>n; 7 //直接給出鄰接矩陣，直接讀。 8 for(int i=1;i<=n;i++) 9 for(int j=1;j<=n;j++) 10 cin>>a[i][j]; 11 //給出兩個頂點和權值 12 for(int i=1;i<=n;i++) 13 { 14 int xx,yy,vv; 15 cin>>xx>>yy>>vv; 16 a[xx][yy]=vv; 17 //雙向圖時 18 a[yy][xx]=vv; 19 } 20 //給出每個頂點的臨界點 21 for(int i=1;i<=n;i++) 22 { 23 int k; 24 cin>>k; 25 for(int j=1;j<=k;j++) 26 { 27 int x; 28 cin>>x; 29 a[i][x]=1; 30 a[x][i]=1; 31 } 32 } 33 return 0; 34 } 鄰接矩陣

2.鄰接表

第一次看這玩意的時候內心萬般草泥馬奔過。

這TM都是什么玩意

后來經過滑稽大師cdc柴大叔的指導下，莫名其妙知道了些什么

然而教材太過簡單，時常還會有些錯的

小弱渣花了一整節自習課照著書上畫了一幅圖，發現！原來！跟書上一毛（mu）一樣。本寶寶不開心，哦是十分不開心。

這大概是這個樣子的

1 #include<iostream> 2 using namespace std; 3 int n; 4 int link[10010],len=0; 5 struct ha 6 { 7 int y,v,next; 8 }e[10010]; 9 void insert(int xx,int yy,int vv) 10 { 11 e[++len].next=link[xx]; 12 link[xx]=len; 13 e[len].y=yy; 14 e[len].v=vv; 15 } 16 int main() 17 { 18 cin>>n; 19 int xx,yy,vv; 20 for(int i=1;i<=n;i++) 21 { 22 cin>>xx>>yy>>vv; 23 insert(xx,yy,vv); 24 insert(yy,xx,vv); 25 } 26 return 0; 27 } 鄰接表

如果出現重邊！鄰接矩陣必須判斷！！

-----------------我是萌萌噠的分割線------------------

DFS：以一個未被訪問過的頂點作為起始頂點，沿當前頂點的邊走到未訪問過的頂點；當沒有未訪問過的頂點時，則回到上一個頂點，繼續試探訪問別的頂點，直到所有的頂點都被訪問過。

1 #include<iostream> 2 using namespace std; 3 bool book[10010];//記錄頂點是否被訪問過 4 int a[10010][10010],n,m; 5 int inf=0x7fffffff; 6 int sum=0; 7 //鄰接矩陣 8 void dfs(int x) 9 { 10 for(int i=1;i<=n;i++) 11 if(book[i]==0 && a[x][i]) 12 { 13 book[i]=1; 14 dfs(i); 15 } 16 } 17 //鄰接表 18 void dfs(int x) 19 { 20 for(int i=link[x];i;i=e[i].next) 21 if(book[e[i].y]==0) 22 { 23 book[e[i].y]=1; 24 dfs(e[i].y); 25 } 26 } 27 int main() 28 { 29 cin>>n; 30 //初始化 31 for(int i=1;i<=n;i++) 32 for(int j=1;j<=n;j++) 33 if(i==j) a[i][j]=0; 34 else a[i][j]=inf; 35 int xx,yy,vv; 36 for(int i=1;i<=m;i++) 37 { 38 cin>>xx>>yy>>vv; 39 a[xx][yy]=vv; 40 a[yy][xx]=vv; 41 } 42 for(int i=1;i<=n;i++) 43 if(book[i]==0) 44 { 45 //求無向圖的連接分量 46 sum++; 47 dfs(i); 48 } 49 return 0; 50 } dfs

BFS：以一個未被訪問過的頂點作為起始頂點，訪問其所有相鄰的頂點，然后對每個相鄰的頂點，在訪問它們相鄰的未被訪問過的頂點，直到所有頂點都被訪問過。

1 #include<iostream> 2 using namespace std; 3 bool book[10010];//記錄頂點是否被訪問過 4 int a[10010][10010],n,m; 5 int inf=0x7fffffff; 6 int sum=0; 7 int q[10010];//隊列，數組一定要開大！！ 8 //鄰接矩陣 9 void bfs(int x) 10 { 11 int head=0,tail=1; 12 q[1]=x; 13 book[i]=1; 14 while(head<tail) 15 { 16 int k=q[++head]; 17 for(int i=1;i<=n;i++) 18 if(a[x][i] &&book[i]==0) 19 { 20 q[++tail]=i; 21 book[i]=1; 22 } 23 } 24 } 25 //鄰接表 26 void dfs(int x) 27 { 28 int head=0,tail=1; 29 q[1]=x; 30 while(head<tail) 31 { 32 for(int i=link[q[head]];i;i=e[i].next) 33 if(book[e[i].y]==0) 34 { 35 book[e[i].y]=1; 36 q[++tail]=e[i].y; 37 } 38 } 39 } 40 int main() 41 { 42 cin>>n; 43 //初始化 44 for(int i=1;i<=n;i++) 45 for(int j=1;j<=n;j++) 46 if(i==j) a[i][j]=0; 47 else a[i][j]=inf; 48 int xx,yy,vv; 49 for(int i=1;i<=m;i++) 50 { 51 cin>>xx>>yy>>vv; 52 a[xx][yy]=vv; 53 a[yy][xx]=vv; 54 } 55 for(int i=1;i<=n;i++) 56 if(book[i]==0) 57 { 58 //求無向圖的連接分量 59 sum++; 60 dfs(i); 61 } 62 return 0; 63 } bfs

?

Bicoloring

傳送門

這道題就是用bfs遍歷一遍，用兩種顏色來填充頂點，有邊相鄰的頂點顏色不能一樣，鄰接矩陣很好寫，很好判斷兩個點，可是空間太大了。

鄰接表想了好久，最終確定了兩個頂點分別是 q[head] 和 e[i].y? i=Link[q[head]]?

1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<algorithm> 8 #include<cmath> 9 using namespace std; 10 typedef long long ll; 11 const int N = 200 + 20; 12 int a[N][N]; 13 int cor[N]; 14 int n, m,flag=1,xx,yy; 15 void dfs(int x) 16 { 17 for (int i = 0; i < n; i++) 18 { 19 if (a[x][i] && cor[i] == 0) 20 { 21 if (cor[x] == 1) 22 cor[i] = 2; 23 else cor[i] = 1; 24 dfs(i); 25 } 26 else if (cor[i] == cor[x] &&a[x][i]) 27 { 28 flag = 0; 29 return; 30 } 31 } 32 } 33 int main() 34 { 35 while (scanf("%d", &n)) 36 { 37 if (n == 0) break; 38 memset(a, 0, sizeof(a)); 39 memset(cor, 0, sizeof(cor)); 40 flag = 1; 41 scanf("%d",&m); 42 while (m--) 43 { 44 scanf("%d %d",&xx,&yy); 45 a[xx][yy] = 1; 46 a[yy][xx] = 1; 47 } 48 cor[0] = 1; 49 dfs(0); 50 if (flag == 0) printf("NOT BICOLORABLE.\n"); 51 else printf("BICOLORABLE.\n"); 52 } 53 54 return 0; 55 } 鄰接矩陣的二分圖 1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<algorithm> 9 #include<cmath> 10 using namespace std; 11 typedef long long ll; 12 const int N = 100000 + 20; 13 int Link[N],cor[N],len=0,bok[N]; 14 int n, m; 15 int q[N]; 16 struct student 17 { 18 int y, next; 19 }e[N]; 20 void insert(int xx, int yy) 21 { 22 e[++len].next = Link[xx]; 23 Link[xx] = len; 24 e[len].y = yy; 25 } 26 int bfs(int x) 27 { 28 int head = 1, tail = 2; 29 q[1] = x; 30 bok[x] = 1; 31 cor[x] = 1; 32 while (head < tail) 33 { 34 for (int i = Link[q[head]]; i; i = e[i].next) 35 { 36 if (cor[e[i].y] == 0) 37 { 38 if (cor[q[head]] == 1) 39 cor[e[i].y] = 2; 40 else 41 cor[e[i].y] = 1; 42 } 43 else if (cor[e[i].y] == cor[q[head]]) 44 return 0; 45 if (bok[e[i].y] == 0) 46 { 47 bok[e[i].y] = 1; 48 q[tail++] = e[i].y; 49 } 50 } 51 head++; 52 } 53 return 1; 54 } 55 int main() 56 { 57 while (scanf("%d", &n)) 58 { 59 memset(bok, 0, sizeof(bok)); 60 memset(Link, 0, sizeof(Link)); 61 memset(q, 0, sizeof(q)); 62 memset(cor, 0, sizeof(cor)); 63 if (n == 0) break; 64 scanf("%d", &m); 65 while (m--) 66 { 67 int xx, yy; 68 scanf("%d %d", &xx, &yy); 69 insert(xx, yy); 70 insert(yy, xx); 71 } 72 if (bfs(0)) printf("BICOLORABLE.\n"); 73 else printf("NOT BICOLORABLE.\n"); 74 } 75 return 0; 76 } 鄰接表的二分圖

拓撲排序：

拓撲就是類似于游戲中點技能，只有先把低級技能點了，才能點高階技能。一個低階技能可能對應多個高階技能，高階技能本身也可以互相對應。

那我們怎么辦呢，另開一個數組indu，表示入度。

剛開始先找入度為0的點，從這個點開始遍歷，然后再找，入度為1的點，再往下找入度為2的點。

每次找到一個，就減去它的入度，相當于把前面那個點刪除掉，相應的邊也刪除掉。

1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<algorithm> 9 #include<cmath> 10 using namespace std; 11 typedef long long ll; 12 const int N = 10000; 13 int Link[110], bok[110],len=0,indu[110],que[N]; 14 int n, m, xx, yy; 15 struct student 16 { 17 int y, next; 18 }e[N]; 19 void insert(int xx, int yy) 20 { 21 e[++len].next = Link[xx]; 22 Link[xx] = len; 23 e[len].y = yy; 24 } 25 void bfs() 26 { 27 int head = 1, tail = 1; 28 for (int i = 1; i <= n; i++) 29 if (indu[i] == 0) 30 { 31 que[tail++] = i; 32 bok[i] = 1; 33 } 34 while (head < tail) 35 { 36 for (int i = Link[que[head]]; i; i = e[i].next) 37 { 38 if (--indu[e[i].y] == 0 && bok[e[i].y] == 0) 39 { 40 que[tail++] = e[i].y; 41 bok[e[i].y] = 1; 42 } 43 } 44 head++; 45 } 46 printf("%d",que[1]); 47 for (int i = 2; i <=n; i++) 48 printf(" %d",que[i]); 49 printf("\n"); 50 } 51 int main() 52 { 53 while (scanf("%d %d",&n,&m)) 54 { 55 if (n == 0) break; 56 memset(e, 0, sizeof(e)); 57 memset(Link, 0, sizeof(Link)); 58 memset(que, 0, sizeof(que)); 59 memset(bok, 0, sizeof(bok)); 60 memset(indu, 0, sizeof(indu)); 61 while (m--) 62 { 63 scanf("%d %d", &xx, &yy); 64 insert(xx, yy); 65 indu[yy]++; 66 } 67 bfs(); 68 } 69 return 0; 70 } 鄰接表的拓撲排序bfs

（他們全都用的stl的vector，我用的鄰接表啊，高端東西，沒有資料全靠自己創。好難過。）

1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<queue> 9 #include<algorithm> 10 #include<cmath> 11 using namespace std; 12 #define ll long long 13 const int N = 12500 + 10; 14 priority_queue<int, vector<int>, greater<int> >q; 15 int Link[510], bok[510],a[510],len=0,indu[510],cnt=0; 16 int n, m, xx, yy; 17 int ans = 0; 18 struct student 19 { 20 int y, next; 21 }e[N]; 22 void insert(int xx, int yy) 23 { 24 e[++len].next = Link[xx]; 25 Link[xx] = len; 26 e[len].y = yy; 27 } 28 void bfs() 29 { 30 cnt = 0; 31 ans = 0; 32 for(int i=1;i<=n;i++) 33 if (indu[i] == 0) 34 { 35 bok[i] = 1; 36 q.push(i); 37 //cout << i << endl; 38 } 39 //cout << endl; 40 while (!q.empty()) 41 { 42 //a[++cnt] = q.top(); 43 int tt = q.top(); 44 q.pop(); 45 ans++; 46 if (ans == 1) 47 printf("%d",tt); 48 else printf(" %d",tt); 49 for (int i = Link[tt]; i; i = e[i].next) 50 { 51 if (--indu[e[i].y] == 0 && bok[e[i].y] == 0) 52 { 53 q.push(e[i].y); 54 bok[e[i].y] = 1; 55 } 56 } 57 } 58 printf("\n"); 59 } 60 int main() 61 { 62 while (scanf("%d %d", &n, &m) != EOF) 63 { 64 memset(Link, 0, sizeof(Link)); 65 memset(bok, 0, sizeof(bok)); 66 memset(e, 0, sizeof(e)); 67 memset(a, 0, sizeof(a)); 68 memset(indu, 0, sizeof(indu)); 69 len = 0; 70 while (m--) 71 { 72 scanf("%d %d",&xx,&yy); 73 indu[yy]++; 74 insert(xx, yy); 75 } 76 bfs(); 77 } 78 79 return 0; 80 } 優先隊列的拓撲排序

舉個例子如圖：

如果你用優先隊列拓撲排序得到的是：3?5?6?4?1?7?8?9?2?0

但是正確答案為?6?4?1?3?9?2?5?7?8?0 這樣使得小的（1）盡量在前面。

優先隊列是讓數字整體小的在前面，而編號最小是讓1盡量在前面，這兩者是不同的，想了好久才知道QAQ。

1 #include "pch.h" 2 #pragma warning(disable:4996) 3 #include<iostream> 4 #include<cstdio> 5 #include<string> 6 #include<cstring> 7 #include<map> 8 #include<set> 9 #include<vector> 10 #include<queue> 11 #include<algorithm> 12 #include<cmath> 13 using namespace std; 14 #define ll long long 15 const int N = 100000 + 10; 16 priority_queue<int, vector<int>, less<int> >q; 17 int Link[30010], bok[30010],a[30010],len=0,indu[30010],cnt=0; 18 int n, m, xx, yy; 19 int ans = 0; 20 struct student 21 { 22 int y, next; 23 }e[N]; 24 void insert(int xx, int yy) 25 { 26 e[++len].next = Link[xx]; 27 Link[xx] = len; 28 e[len].y = yy; 29 } 30 void bfs() 31 { 32 cnt = 0; 33 ans = 0; 34 for(int i=1;i<=n;i++) 35 if (indu[i] == 0) 36 { 37 bok[i] = 1; 38 q.push(i); 39 //cout << i << endl; 40 } 41 //cout << endl; 42 while (!q.empty()) 43 { 44 //a[++cnt] = q.top(); 45 int tt = q.top(); 46 q.pop(); 47 a[++ans] = tt; 48 for (int i = Link[tt]; i; i = e[i].next) 49 { 50 if (--indu[e[i].y] == 0 && bok[e[i].y] == 0) 51 { 52 q.push(e[i].y); 53 bok[e[i].y] = 1; 54 } 55 } 56 } 57 for (int i = ans; i >= 1; i--) 58 { 59 if (i == ans) 60 printf("%d",a[i]); 61 else printf(" %d",a[i]); 62 } 63 printf("\n"); 64 } 65 int main() 66 { 67 int t; 68 scanf("%d",&t); 69 while (t--) 70 { 71 scanf("%d %d", &n, &m); 72 memset(Link, 0, sizeof(Link)); 73 memset(bok, 0, sizeof(bok)); 74 memset(e, 0, sizeof(e)); 75 memset(a, 0, sizeof(a)); 76 memset(indu, 0, sizeof(indu)); 77 len = 0; 78 while (m--) 79 { 80 scanf("%d %d",&xx,&yy); 81 indu[xx]++; 82 insert(yy, xx); 83 } 84 bfs(); 85 } 86 87 return 0; 88 } 編號最小反向建圖的拓撲排序

還搞了搞優先隊列

1 priority_queue <int,vector<int>,greater<int> > q; 2 priority_queue <int,vector<int>,less<int> >q;

歐拉回路：

歐拉回路是指不令筆離開紙面，可畫過圖中每條邊僅一次，且可以回到起點的一條回路。現給定一個圖，問是否存在歐拉回路？

如何判斷歐拉回路呢：首先它是連通圖，其次對于無向圖來說，所有頂點度數為偶數。

判斷聯通可以用并查集，判斷度數很好寫。

1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<queue> 9 #include<algorithm> 10 #include<cmath> 11 using namespace std; 12 #define ll long long 13 const int N = 1010; 14 int a[N][N],indu[N],par[N]; 15 int n, m, xx, yy; 16 int find(int x) 17 { 18 if (par[x] == x) return x; 19 return par[x] = find(par[x]); 20 } 21 void hebing(int a, int b) 22 { 23 a = find(a); 24 b = find(b); 25 if (a != b) 26 par[a] = b; 27 } 28 int main() 29 { 30 while (scanf("%d", &n)) 31 { 32 if (n == 0) break; 33 scanf("%d", &m); 34 memset(a, 0, sizeof(a)); 35 memset(indu, 0, sizeof(indu)); 36 for (int i = 1; i <= n; i++) 37 par[i] = i; 38 while (m--) 39 { 40 scanf("%d %d", &xx, &yy); 41 indu[xx]++; 42 indu[yy]++; 43 hebing(xx, yy); 44 } 45 int cnt = 0; 46 for (int i = 1; i <= n; i++) 47 if (par[i] == i) 48 cnt++; 49 if (cnt > 1) 50 { 51 printf("0\n"); 52 continue; 53 } 54 cnt = 0; 55 for (int i = 1; i <= n; i++) 56 if (indu[i] % 2 == 1) 57 cnt++; 58 if (cnt > 0) 59 printf("0\n"); 60 else printf("1\n"); 61 } 62 63 return 0; 64 } 判斷歐拉回路

輸出歐拉回路：

就是從一個頂點起，一筆走過所有的邊。dfs遍歷邊！

以前的dfs和bfs都是遍歷頂點，而這個是遍歷邊！

這個只能用dfs，我想了想因為你一筆走的就是一個dfs的過程，不存在bfs的過程，如果有bfs的話，那就畫一條回去，在畫另一條。跟題意不否。

判斷歐拉回路的個數：

傳送門

對于每個以i為根的連通分量我們記錄屬于該連通分量的點數目num[i]和該連通分量中奇度點的個數odd[i]. 如果num[i]==0或1,需0筆.(注意num[i]==0表示i點不是根,num[i]==1表示i點是一個孤立的點.) 如果num[i]>1且odd[i]==0 需1筆如果num[i]>1且odd[i]>0 需odd[i]/2筆

1205.田野上的環

傳送門

剛開始的時候小弱渣剛剛理解什么是鄰接矩陣，對于dfs還不熟

然而現在看書上鄰接矩陣+dfs 簡直扯淡

總而言之這道題就是找與1不相連的點

dfs 兩個變量用（1，i）來遍歷；

找與1相連，然后依次遞歸

最后看誰還沒有遍歷，按順序輸出

最后用布爾判斷是不是沒有！

1 #include<iostream> 2 using namespace std; 3 int a[300][300],n,m,x,y; 4 bool b=0,f[300]; 5 void dfs(int x,int y) 6 { 7 if(a[x][y]==1&&f[y]!=1) 8 { 9 f[y]=1; 10 for(int i=1;i<=n;i++) 11 dfs(y,i); 12 } 13 else return; 14 } 15 int main() 16 { 17 cin>>n>>m; 18 for(int i=1;i<=m;i++) 19 { 20 cin>>x>>y; 21 a[x][y]=1; 22 a[y][x]=1; 23 } 24 for(int i=1;i<=n;i++) 25 a[i][i]=1; 26 for(int i=2;i<=n;i++) 27 dfs(1,i); 28 for(int i=2;i<=n;i++) 29 if(f[i]==0) 30 { b=1; 31 cout<<i<<endl; 32 } 33 if(b==0) cout<<0<<endl; 34 return 0; 35 } 1205

1206.1207.1208.犯罪集團

傳送門

就是找幾個連通分量，注意數組開大，小弱渣卡了好幾次。

1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 int n,m,x,y,len=0; 5 int link[50100],ans=0,q[50100]; 6 bool f[50100]; 7 struct edge 8 { 9 int y,next; 10 }e[50100]; 11 void in(int xx,int yy) 12 { 13 e[++len].next=link[xx]; 14 link[xx]=len; 15 e[len].y=yy; 16 } 17 void bfs(int k) 18 { 19 memset(q,0,sizeof(q)); 20 int head=0,tail=1; 21 q[1]=k; 22 while(head++<tail) 23 for(int i=link[q[head]];i;i=e[i].next) 24 if(!f[e[i].y]) 25 { 26 f[e[i].y]=1; 27 q[++tail]=e[i].y; 28 } 29 } 30 int main() 31 { 32 cin>>n>>m; 33 for(int i=1;i<=m;i++) 34 { 35 cin>>x>>y; 36 in(x,y); 37 in(y,x); 38 } 39 for(int i=1;i<=n;i++) 40 if(!f[i]) 41 { 42 ans++; 43 bfs(i); 44 } 45 cout<<ans<<endl; 46 return 0; 47 } 1208

?

1210.騎馬修柵欄

傳送門

書上寫著歐拉路與歐拉回路，把求最小路都做出來了死活還都不知道歐拉路是什么鬼

嗯去科技館的時候好像看過一個叫歐拉路的玩意

然而跟題目有毛關系（怒拍桌子！）

啊因為不會歐拉路，so現在看這道題還是不會

你看這個人怎么這么懶。沒辦法你來打我啊

算了我們還是跳過這道題吧

1 /* 2 by kaike 3 11/15/2016 4 */ 5 //這題是讓求出一條歐拉路。 6 #include<iostream> 7 using namespace std; 8 int xx,yy,m; 9 int l[1028][1028],du[1028],maxx=0; 10 int a[1028],t=0; 11 //找到和它相連的，依次刪除他們之間的連線。 12 //再找新的點，最后把這個點加入輸出隊列。 13 void find(int k) 14 { 15 for(int i=1;i<=maxx;i++) 16 if(l[k][i]) 17 { 18 l[k][i]--; 19 l[i][k]--; 20 find(i); 21 } 22 a[++t]=k; 23 } 24 int main() 25 { 26 cin>>m; 27 for(int i=1;i<=m;i++) 28 { 29 cin>>xx>>yy; 30 l[xx][yy]++; 31 l[yy][xx]++; 32 du[xx]++; 33 du[yy]++; 34 if(xx>maxx) maxx=xx; 35 if(yy>maxx) maxx=yy; 36 } 37 int s=1; 38 //數據保證至少有1個解，那就一定存在歐拉路。 39 //我們要選一個點為起點，要在字典序中找出最小的，就要找最小的點為起點。 40 for(int i=1;i<=maxx;i++) 41 if(du[i]%2==1) 42 { 43 s=i; 44 break; 45 } 46 //對于當前的點，把所有點從小到大搜索。 47 find(s); 48 //這樣做之后，順序是反著的。 49 for(int i=m+1;i>0;i--) 50 cout<<a[i]<<endl; 51 return 0; 52 } 1210

1209.幾何圖形還原

傳送門

這道題需要多注意！多注意！多注意！

因為還需要回溯啊

Why？

害怕這條路走不通，換一條路試試咯

所有的邊都連起來了，就說明最后一個頂點跟1頂點肯定是連起來的

因為要輸出字典序最小的那個，所以只要從1開始遍歷就哦可，算是個隱藏的小細節

dfs 每遍歷一個點就用數組記錄下來，然后繼續遍歷

回溯。

最后判斷最后一個點跟1是否相連，相連輸出退出。

1 #include<iostream> 2 #include<stdlib.h> 3 using namespace std; 4 int n,ans[60],t=1; 5 int a[60][60],xx,yy; 6 int f[60]; 7 bool book[60]; 8 void dfs(int k) 9 { 10 if(t==n) 11 { 12 if(f[ans[t]]!=1) return; 13 else 14 { for(int i=1;i<=n;i++) 15 cout<<ans[i]<<' '; 16 exit(0); 17 } 18 } 19 for(int i=1;i<=n;i++) 20 if(a[k][i]==1&& book[i]==0) 21 { 22 book[i]=1; 23 ans[++t]=i; 24 dfs(i); 25 book[i]=0; 26 t--; 27 } 28 } 29 int main() 30 { 31 cin>>n; 32 while(cin>>xx>>yy) 33 { 34 a[xx][yy]=1; 35 a[yy][xx]=1; 36 } 37 for(int i=1;i<=n;i++) 38 f[i]=a[i][1]; 39 book[1]=1; 40 ans[1]=1; 41 dfs(1); 42 return 0; 43 } 1209

?

1211.街道賽跑

傳送門

題太復雜，看題解都看不懂，回來寫。

這里這里

--------------------我是萌萌噠的分割線---------------

嗯真開心，終于要到最短路了。

累了本寶寶了。

1212. Geodetic集合

傳送門

這應該是一個求最短路的吧，然而教材上寫圖的傳遞閉包，什么鬼

就是求從 i-j 最短路中可能經過的點順序輸出。

要多注意！多注意！多注意！

先用 floyed 求出每個點的最短路

然后依次枚舉，如果最短路相同用三維數組存起來點

然后輸出

1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int a[50][50],b[50][50][50],c[50][50]; 5 int n,m,q; 6 int main() 7 { 8 cin>>n>>m; 9 for(int i=1;i<=n;i++) 10 for(int j=1;j<=n;j++) 11 if(i==j) a[i][j]=0; 12 else a[i][j]=100; 13 int xx,yy; 14 for(int i=1;i<=m;i++) 15 { 16 cin>>xx>>yy; 17 a[xx][yy]=1; 18 a[yy][xx]=1; 19 } 20 for(int k=1;k<=n;k++) 21 for(int i=1;i<=n;i++) 22 for(int j=1;j<=n;j++) 23 if(a[i][j]>a[i][k]+a[k][j]) 24 a[i][j]=a[i][k]+a[k][j]; 25 for(int k=1;k<=n;k++) 26 for(int i=1;i<=n;i++) 27 for(int j=1;j<=n;j++) 28 if(a[i][j]==a[i][k]+a[k][j] && k!=i && k!=j && i!=j ) 29 b[i][j][c[i][j]++]=k; 30 cin>>q; 31 int x,y; 32 for(int i=1;i<=q;i++) 33 { 34 cin>>x>>y; 35 b[x][y][c[x][y]++]=x; 36 b[x][y][c[x][y]++]=y; 37 sort(b[x][y],b[x][y]+c[x][y]+1); 38 for(int j=1;j<=c[x][y];j++) 39 cout<<b[x][y][j]<<' '; 40 cout<<endl; 41 } 42 return 0; 43 } 1212

FLOYED

就是找中間點看是否可以松弛，適用于連接矩陣。

1 for(int k=1;k<=n;k++) 2 for(int i=1;i<=n;i++) 3 for(int j=1;j<=n;j++) 4 if(a[i][j]>a[i][k]+a[k][j]) 5 a[i][j]=a[i][k]+a[k][j]; floyed

1213.最優乘車

傳送門

直接floyed 然后輸出 a[1][n]-1

1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int a[510][510],n,m,t[510],l; 5 char c; 6 int main() 7 { 8 cin>>m>>n; 9 for(int i=1;i<=n;i++) 10 for(int j=1;j<=n;j++) 11 if(i==j) a[i][j]=0; 12 else a[i][j]=1000; 13 for(int i=1;i<=m;i++) 14 { 15 c=' '; 16 l=0; 17 while(c!=10) 18 { 19 cin>>t[++l]; 20 c=getchar(); 21 } 22 for(int j=1;j<l;j++) 23 for(int k=j+1;k<=l;k++) 24 a[t[j]][t[k]]=1; 25 } 26 for(int k=1;k<=n;k++) 27 for(int i=1;i<=n;i++) 28 for(int j=1;j<=n;j++) 29 if(a[i][j]>a[i][k]+a[k][j]) 30 a[i][j]=a[i][k]+a[k][j]; 31 if((a[1][n]==1000)||(a[1][n]==0)) cout<<"NO"<<endl; 32 else cout<<a[1][n]-1<<endl; 33 return 0; 34 } 1213

1214. Bessie Come Home

傳送門

這道題最大的坑點就是有a-Z 個糧倉

然后把字符轉換為數字，floyed

從大寫字母中找去糧倉最小的路程輸出，并輸出 i；

1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #define MAX 0xfffffff 5 using namespace std; 6 int p,m[55][55],w[55],t,minnum=MAX; 7 char t1,t2,ans; 8 char ch(char t) 9 { 10 if(isupper(t)) 11 { 12 t=t-'A'+26; 13 w[t]=1; 14 return t; 15 } 16 return t-'a'; 17 } 18 int main(void) 19 { 20 cin>>p; 21 memset(m,-1,sizeof(m)); 22 for(int i=0;i<52;i++) 23 m[i][i]=0; 24 for(int i=0;i<p;i++) 25 { 26 cin>>t1>>t2>>t; 27 t1=ch(t1); 28 t2=ch(t2); 29 if(m[t1][t2]==-1 || m[t1][t2]>t) 30 { 31 m[t1][t2]=t; 32 m[t2][t1]=t; 33 } 34 } 35 for(int i=0;i<55;i++) 36 for(int j=0;j<55;j++) 37 for(int k=0;k<55;k++) 38 if(m[i][k]!=-1 && m[j][k]!=-1) 39 if(m[i][j]==-1 || (m[j][k]+m[i][k]<m[i][j])) 40 m[i][j]=m[j][k]+m[i][k]; 41 for(int i=26;i<51;i++) 42 if(w[i] && m[i][51]<minnum) 43 { 44 minnum=m[i][51]; 45 ans=(char)(i-26+'A'); 46 } 47 cout<<ans<<' '<<minnum<<endl; 48 return 0; 49 } 1214

DIJKSTRA

這是求指定一個點到其余各個頂點的最短路徑

（單源非負）

用book 數組標記

用 dis 數組標記距離

找出離 1 最近的點，然后依次松弛 floyed

1 #include<iostream> 2 using namespace std; 3 int a[10010][10010],dis[10010]; 4 bool book[10010]; 5 int inf=0x7fffffff; 6 int minn=inf; 7 int main() 8 { 9 int n,m; 10 cin>>n>>m; 11 for(int i=1;i<=n;i++) 12 for(int j=1;j<=n;j++) 13 if(i==j) a[i][j]=0; 14 else a[i][j]=inf; 15 int xx,yy,vv; 16 for(int i=1;i<=m;i++) 17 { 18 cin>>xx>>yy>>vv; 19 a[xx][yy]=vv; 20 //a[yy][xx]=vv; 21 } 22 for(int i=1;i<=n;i++) 23 { dis[i]=a[1][i]; 24 book[i]=0; 25 } 26 book[1]=1; 27 int u; 28 //dijkstra 29 for(int i=1;i<=n;i++) 30 { 31 minn=inf; 32 for(int j=1;j<=n;j++) 33 if(book[j]==0 && dis[j]<minn ) 34 { 35 minn=dis[j]; 36 u=j; 37 } 38 book[u]=1; 39 for(int j=1;j<=n;j++) 40 if(a[u][j]<inf) 41 if(dis[j]>dis[u]+a[u][j]) 42 dis[j]=dis[u]+a[u][j]; 43 } 44 for(int i=1;i<=n;i++) 45 cout<<dis[i]<<endl; 46 return 0; 47 } dijkstra

鄰接表：

1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<queue> 9 #include<algorithm> 10 #include<cmath> 11 using namespace std; 12 typedef long long ll; 13 const int inf=0x7fffffff; 14 const int N=200+10; 15 const int M=20000; 16 int n,m,xx,yy,vv; 17 int Link[N],len=0,bok[N],dis[N]; 18 struct student 19 { 20 int y,v,next; 21 }e[M]; 22 void insert(int xx,int yy,int vv) 23 { 24 e[++len].next=Link[xx]; 25 Link[xx]=len; 26 e[len].y=yy; 27 e[len].v=vv; 28 } 29 void init() 30 { 31 scanf("%d %d",&n,&m); 32 while(m--) 33 { 34 scanf("%d %d %d",&xx,&yy,&vv); 35 insert(xx,yy,vv); 36 } 37 } 38 void print() 39 { 40 for(int i=1;i<=n;i++) 41 printf("%d ",dis[i]); 42 printf("\n"); 43 } 44 void dijkstra() 45 { 46 bok[1]=1; 47 int u; 48 for(int i=2;i<=n;i++) 49 dis[i]=inf; 50 for(int i=Link[1];i;i=e[i].next) 51 dis[e[i].y]=e[i].v; 52 for(int i=1;i<n;i++) 53 { 54 int minn=inf; 55 for(int j=1;j<=n;j++) 56 if(bok[j]==0&&dis[j]<minn) 57 { 58 minn=dis[j]; 59 u=j; 60 } 61 bok[u]=1; 62 for(int i=Link[u];i;i=e[i].next) 63 { 64 if(dis[e[i].y]>dis[u]+e[i].v) 65 dis[e[i].y]=dis[u]+e[i].v; 66 } 67 } 68 } 69 int main() 70 { 71 init(); 72 dijkstra(); 73 print(); 74 return 0; 75 } View Code

DIJKSTRA：

1.找出最近的那個點

2.更新

1217.晚餐

傳送門

就是dijkstra ，然后求距離小于 t 的有幾個

1 #include<iostream> 2 using namespace std; 3 int t,f,p,ans=0; 4 int a[550][550],dis[550]; 5 bool book[550]; 6 int main() 7 { 8 cin>>t>>f>>p; 9 for(int i=1;i<=f;i++) 10 for(int j=1;j<=f;j++) 11 if(i==j) a[i][j]=0; 12 else a[i][j]=9999999; 13 int xx,yy,vv; 14 for(int i=1;i<=p;i++) 15 { 16 cin>>xx>>yy>>vv; 17 if(xx!=yy) 18 if(a[xx][yy]>vv) 19 { a[xx][yy]=vv; a[yy][xx]=vv;} 20 } 21 for(int i=1;i<=f;i++) 22 { dis[i]=a[1][i]; 23 book[i]=0; 24 } 25 book[1]=1; 26 for(int i=1;i<f;i++) 27 { 28 int u=1; 29 int min=9999999; 30 for(int j=1;j<=f;j++) 31 if(min>dis[j] && book[j]==0) 32 { 33 min=dis[j]; 34 u=j; 35 } 36 book[u]=1; 37 for(int v=1;v<=f;v++) 38 if(a[u][v]<9999999) 39 if(dis[v]>dis[u]+a[u][v]) 40 dis[v]=dis[u]+a[u][v]; 41 } 42 for(int i=1;i<=f;i++) 43 if(dis[i]<=t) ans++; 44 cout<<ans<<endl; 45 return 0; 46 } 1217

BELLMAN-FORD

這個主要是判斷負環

1 #include<iostream> 2 using namespace std; 3 int n,m; 4 int a[10010][10010],dis[10010]; 5 int x[10010],y[10010],v[10010]; 6 int main() 7 { 8 cin>>n>>m; 9 int xx,yy,vv; 10 for(int i=1;i<=m;i++) 11 cin>>x[i]>>y[i]>>v[i]; 12 for(int i=1;i<=n;i++) 13 dis[i]=0x7fffffff; 14 dis[1]=0; 15 for(int k=1;k<n;k++) 16 for(int i=1;i<=m;i++) 17 if(dis[y[i]]>dis[x[i]]+v[i]) 18 dis[y[i]]=dis[x[i]]+v[i]; 19 for(int i=1;i<=n;i++) 20 cout<<dis[i]<<endl; 21 return 0; 22 } bellman-ford

SPFA

就是bellman-ford 的隊列用鄰接表

1 /* 2 by kaike 3 11/16/2016 4 */ 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 const int MAXN=10010; 9 int que[MAXN],dis[MAXN],bok[MAXN],Link[MAXN],len=0,head=0,tail=1; 10 int m,n,x,y,v; 11 struct qaq 12 { 13 int next,y,v; 14 }e[MAXN]; 15 void insert(int xx,int yy,int vv) 16 { 17 e[++len].next=Link[xx]; 18 Link[xx]=len; 19 e[len].y=yy; 20 e[lrn].v=vv; 21 } 22 void init() 23 { 24 cin>>n>>m; 25 for(int i=1;i<=m;i++) 26 { cin>>x>>y>>v; 27 insert(x,y,v); 28 insert(y,x,v); 29 } 30 } 31 void spfa() 32 { 33 dis[S]=0; 34 bok[S]=1; 35 que[1]=S; 36 head=0; tail=1; 37 while(head<tail) 38 { 39 int t=q[++head]; 40 bok[t]=0; 41 for(int i=Link[t];i;i=e[i].next) 42 { 43 if(dis[e[i].y]>dis[t]+e[i].v) 44 { 45 dis[e[i].y]=dis[t]+e[i].v; 46 if(bok[e[i].y]==0) 47 { 48 que[++tail]=e[i].y; 49 bok[e[i].y]=1; 50 } 51 } 52 } 53 } 54 } 55 int main() 56 { 57 init(); 58 spfa(); 59 return 0; 60 } 我以后再也不學亂七八糟的算法了= =

具體看1216.蟲洞

1216.蟲洞

傳送門

就是輸入兩組數據，一組雙向，一組單項負環，用spfa 如果有負環，就說明可以，沒有就不可以

1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 int f,n,m,w; 5 int len=0; 6 int link[510],dis[510]; 7 bool flag,book[510]; 8 struct data 9 { 10 int y,v,next; 11 }e[100100]; 12 void ins(int xx,int yy,int vv) 13 { 14 e[++len].next=link[xx]; 15 link[xx]=len; 16 e[len].y=yy; 17 e[len].v=vv; 18 } 19 void spfa(int x) 20 { 21 book[x]=1; 22 for(int i=link[x];i;i=e[i].next) 23 { 24 if(e[i].v+dis[x]<dis[e[i].y]) 25 { if(book[e[i].y]) { 26 flag=1; 27 return ; 28 } 29 else 30 { 31 dis[e[i].y]=e[i].v+dis[x]; 32 spfa(e[i].y); 33 } 34 } 35 } 36 book[x]=0; 37 } 38 bool judge() 39 { 40 for(int i=1;i<=n;i++) 41 dis[i]=book[i]=0; 42 flag=0; 43 for(int i=1;i<=n;i++) 44 { 45 spfa(i); 46 if(flag) return 1; 47 } 48 return 0; 49 } 50 int main() 51 { 52 cin>>f; 53 while(f--) 54 { 55 len=0; 56 memset(link,0,sizeof(link)); 57 cin>>n>>m>>w; 58 int xx,yy,vv; 59 for(int i=1;i<=m;i++) 60 { 61 cin>>xx>>yy>>vv; 62 ins(xx,yy,vv); 63 ins(yy,xx,vv); 64 } 65 for(int i=1;i<=w;i++) 66 { 67 cin>>xx>>yy>>vv; 68 ins(xx,yy,-vv); 69 } 70 if(judge()) cout<<"YES"<<endl; 71 else cout<<"NO"<<endl; 72 } 73 return 0; 74 } 1216

?如果進隊次數>n 就說明有負環。可以用隊列，反而dfs不知道怎么寫。

1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<queue> 9 #include<algorithm> 10 #include<cmath> 11 using namespace std; 12 typedef long long ll; 13 const int inf=0x7fffffff; 14 const int N=500+10; 15 const int M=100100; 16 int T,n,m,w,xx,yy,vv; 17 int Link[N],len=0,bok[N],dis[N],upp[N],que[M]; 18 struct student 19 { 20 int y,v,next; 21 }e[M]; 22 void insert(int xx,int yy,int vv) 23 { 24 e[++len].next=Link[xx]; 25 Link[xx]=len; 26 e[len].y=yy; 27 e[len].v=vv; 28 } 29 void init() 30 { 31 memset(e,0,sizeof(e)); 32 memset(Link,0,sizeof(Link)); 33 len=0; 34 scanf("%d %d %d",&n,&m,&w); 35 while(m--) 36 { 37 scanf("%d %d %d",&xx,&yy,&vv); 38 insert(xx,yy,vv); 39 insert(yy,xx,vv); 40 } 41 while(w--) 42 { 43 scanf("%d %d %d",&xx,&yy,&vv); 44 insert(xx,yy,-vv); 45 } 46 } 47 void print() 48 { 49 for(int i=1;i<=n;i++) 50 printf("%d ",dis[i]); 51 printf("\n"); 52 } 53 int spfa() 54 { 55 memset(upp,0,sizeof(upp)); 56 memset(bok,0,sizeof(bok)); 57 memset(que,0,sizeof(que)); 58 for(int i=1;i<=n;i++) 59 dis[i]=inf; 60 int head=1,tail=2; 61 dis[1]=0; 62 que[1]=1; 63 bok[1]=1; 64 while(head<tail) 65 { 66 int tt=que[head]; 67 bok[tt]=0; 68 for(int i=Link[tt];i;i=e[i].next) 69 { 70 if(dis[e[i].y]>dis[tt]+e[i].v) 71 { 72 dis[e[i].y]=dis[tt]+e[i].v; 73 if(bok[e[i].y]==0) 74 { 75 que[tail++]=e[i].y; 76 bok[e[i].y]=1; 77 upp[e[i].y]++; 78 } 79 if(upp[e[i].y]>n) 80 return 0; 81 } 82 } 83 head++; 84 } 85 return 1; 86 } 87 int main() 88 { 89 scanf("%d",&T); 90 while(T--) 91 { 92 init(); 93 if(spfa()) 94 printf("NO\n"); 95 else printf("YES\n"); 96 } 97 return 0; 98 } View Code

（超時code）

1215.香甜的黃油

傳送門

構建一個雙向圖

然后spfa 好像是第一個超時是因為沒有 book 數組標記

然后記錄所有需要的最小值

1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 int n,p,c; 5 int a[850][850],b[510],dis[850],q[100100]; 6 int maxx=99999999,sum; 7 void spfa(int x) 8 { 9 memset(dis,260,sizeof(dis)); 10 int head=0,tail=1; 11 q[0]=x; 12 dis[x]=0; 13 while(head<tail) 14 { 15 for(int i=1;i<=p;i++) 16 if(dis[i]>a[q[head]][i]+dis[q[head]]) 17 { 18 q[tail++]=i; 19 dis[i]=a[q[head]][i]+dis[q[head]]; 20 } 21 head++; 22 } 23 sum=0; 24 for(int i=1;i<=n;i++) 25 sum+=dis[b[i]]; 26 } 27 int main() 28 { 29 memset(a,260,sizeof(a)); 30 cin>>n>>p>>c; 31 for(int i=1;i<=n;i++) 32 cin>>b[i]; 33 int xx,yy,vv; 34 for(int i=1;i<=c;i++) 35 { 36 cin>>xx>>yy>>vv; 37 a[xx][yy]=a[yy][xx]=vv; 38 } 39 for(int i=1;i<=p;i++) 40 { 41 spfa(i); 42 if(maxx>sum) maxx=sum; 43 } 44 cout<<maxx<<endl; 45 return 0; 46 } 1215（超時） 1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int n,p,c; 6 bool book[1010]; 7 int len=0,ans=0x7fffffff; 8 int b[850],q[100010],dis[1000],link[1000]; 9 struct ha 10 { 11 int y,next,v; 12 }e[15000]; 13 void insert(int xx,int yy,int vv) 14 { 15 e[++len].next=link[xx]; 16 link[xx]=len; 17 e[len].y=yy; 18 e[len].v=vv; 19 } 20 int spfa(int x) 21 { 22 memset(dis,10,sizeof(dis)); 23 memset(book,0,sizeof(book)); 24 dis[x]=0; 25 book[x]=1; 26 q[1]=x; 27 int head=0,tail=1,sum=0; 28 while(head<tail) 29 { 30 int tn=q[++head]; 31 book[tn]=0; 32 int te=link[tn]; 33 for(int i=te;i;i=e[i].next) 34 { 35 int tmp=e[i].y; 36 if(dis[tmp]>dis[tn]+e[i].v) 37 { 38 dis[tmp]=dis[tn]+e[i].v; 39 if(!book[tmp]) 40 { 41 book[tmp]=1; 42 q[++tail]=tmp; 43 } 44 } 45 } 46 } 47 for(int i=1;i<=n;i++) 48 sum+=dis[b[i]]; 49 return sum; 50 } 51 int main() 52 { 53 cin>>n>>p>>c; 54 for(int i=1;i<=n;i++) 55 cin>>b[i]; 56 int xx,yy,vv; 57 for(int i=1;i<=c;i++) 58 { 59 cin>>xx>>yy>>vv; 60 insert(xx,yy,vv); 61 insert(yy,xx,vv); 62 } 63 for(int i=1;i<=p;i++) 64 ans=min(spfa(i),ans); 65 cout<<ans<<endl; 66 return 0; 67 } 1215

易錯點阿喂

1.鄰接矩陣必須判斷重邊（看要最大值還是最小值）

2.鄰接矩陣注意范圍（5000以上就會爆）

不過可以用鄰接表對拍

3.link是關鍵字，這個壞習慣要改掉！！

4.注意e數組的范圍，無向圖 e*2，有向圖e?

---------------------分割線----------------------------

最小生成樹。

prim

1 void prim(int S) 2 { 3 memset(dis,10,sizeof(dis)); 4 memset(bok,0,sizeof(bok)); 5 bok[S]=1; 6 for(int i=1;i<=n;i++) 7 dis[i]=a[S][i]; 8 summ=0; 9 for(int i=1;i<n;i++) 10 { 11 int minn=a[0][0],c=0; 12 for(int j=1;j<=n;j++) 13 if(minn>dis[j]&&bok[j]==0) 14 { 15 minn=dis[j]; 16 c=j; 17 } 18 bok[c]=1; 19 summ+=minn; 20 for(int j=1;j<=n;j++) 21 if(dis[j]>a[c][j]&&bok[j]==0) 22 dis[j]=a[c][j]; 23 } 24 } = =

kruskal

1 /* 2 by kaike 3 11/16/2016 4 */ 5 #include<iostream> 6 #include<algorithm> 7 #include<cstring> 8 #include<string> 9 #include<cstdio> 10 using namespace std; 11 int kk=0,sum=0; 12 int getf(int v) 13 { 14 if(f[v]!=v) 15 f[v]=getf(f[v]); 16 return f[v]; 17 } 18 int merge(int v,int u) 19 { 20 int t1=getf(v),t2=getf(u); 21 if(t1!=t2) 22 { f[t2]=t1; 23 return 1; 24 } 25 return 0; 26 } 27 void kruskal() 28 { 29 for(int i=1;i<=n;i++) 30 { 31 if(meige(e[i].next,e[i].y)) 32 { 33 kk++; 34 sum+=e[i].v; 35 } 36 if(kk==n-1) break; 37 } 38 } 39 int main() 40 { 41 kruskal(); 42 cout<<sum<<endl; 43 return 0; 44 } = =

?割點

1 /* 2 by kaike 3 11/16/2016 4 */ 5 #include<iostream> 6 #include<algorithm> 7 #include<cstdio> 8 #include<cstring> 9 #include<string> 10 using namespace std; 11 const int MAXN=5010; 12 int n,e[MAXN][MAXN]; 13 int num[MAXN],low[MAXN],bok[MAXN]; 14 int root=1,ans=0,x,y,index=0; 15 void init() 16 { 17 cin>>n; 18 while(cin>>x>>y) 19 { 20 e[x][y]=1; 21 e[y][x]=1; 22 } 23 } 24 void dfnlow(int cur,int father) 25 { 26 int child=0; 27 index++; 28 num[cur]=index; 29 low[cur]=index; 30 for(int i=1;i<=n;i++) 31 if(e[cur][i]==1) 32 { 33 if(num[i]==0) 34 { 35 child++; 36 dfnlow(i,cur); 37 low[cur]=min(low[cur],low[i]); 38 if(cur!=root&& low[i]>=num[cur]) 39 bok[cur]=1; 40 if(cur==root && child==2) 41 bok[cur]=1; 42 } 43 else if(i!=father) 44 low[cur]=min(low[cur],num[i]); 45 } 46 } 47 int main() 48 { 49 init(); 50 dfnlow(1,root); 51 for(int i=1;i<=n;i++) 52 if(bok[i]==1) ans++; 53 cout<<ans<<endl; 54 for(int i=1;i<=n;i++) 55 if(bok[i]==1) cout<<i<<endl; 56 return 0; 57 } = =

割邊

1 /* 2 by kaike 3 11/16/2016 4 */ 5 #include<iostream> 6 #include<algorithm> 7 #include<cstring> 8 #include<string> 9 #include<cstdio> 10 using namespace std; 11 const int MAXN=5010; 12 int n,m,e[160][160],x,y,len=0; 13 int num[MAXN],low[MAXN],index=0,bok[MAXN],root=1; 14 struct qaq 15 { 16 int aa,bb; 17 }a[MAXN]; 18 bool cmp(qaq x,qaq y) 19 { 20 return (x.aa<y.aa ||(x.aa==y.aa && x.bb<y.bb )); 21 } 22 void init() 23 { 24 cin>>n>>m; 25 for(int i=1;i<=m;i++) 26 { 27 cin>>x>>y; 28 e[x][y]=1; 29 e[y][x]=1; 30 } 31 } 32 void dfnlow(int cur,int father) 33 { 34 int child=0; 35 index++; 36 num[cur]=index; 37 low[cur]=index; 38 for(int i=1;i<=n;i++) 39 if(e[cur][i]==1) 40 { 41 if(num[i]==0) 42 { 43 child++; 44 dfnlow(i,cur); 45 low[cur]=min(low[cur],low[i]); 46 if(low[i]>num[cur]) 47 { a[++len].aa=cur; 48 a[len].bb=i; 49 } 50 } 51 else if(i!=father) 52 low[cur]=min(low[cur],num[i]); 53 } 54 } 55 int main() 56 { 57 init(); 58 dfnlow(1,root); 59 sort(a+1,a+len+1,cmp); 60 for(int i=1;i<=len;i++) 61 cout<<a[i].aa<<' '<<a[i].bb<<endl; 62 return 0; 63 } = =

有向圖的強聯通分量

無向圖的邊雙聯通分量

這樣看來好像圖也沒有很難

不懂為什么學東西的時候遇到題目都不會

歸根結底還是知識點不熟悉

感覺這樣一總結都清晰了好多

嗯

不言謝

只赴湯蹈火

轉載于:https://www.cnblogs.com/Kaike/p/5916221.html

總結

以上是生活随笔為你收集整理的靠二进制画几何[图论]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： javascript之回调函数小知识
下一篇：【week3】psp （技术随笔）