Tyvj 2059 元芳看電影

描述

神探狄仁杰電影版首映這天，狄仁杰、李元芳和狄如燕去看電影。由于人實在是太多了，入場的隊伍變得十分不整齊，一個人的前面可能會出現(xiàn)并排的好多人。
“元芳，這隊伍你怎么看？”
“大人，卑職看不出這隊伍是怎么排的！但是卑職看出了一些兩個人之間的前后關(guān)系！”
“那么我們可以寫個程序計算出來一定沒有和其它人并排的人數(shù)。”
“大人/叔父真乃神人也！”

輸入格式

第一行兩個數(shù)N、M，表示隊伍一共有N個人，元芳看出了M對關(guān)系。
接下來M行每行兩個數(shù)a、b，表示a在b的前面（不一定正好在b的前面，ab之間可能有其他人）。

輸出格式

有多少個人一定沒有和其他人并排。

測試樣例1

輸入

3 2
1 2
1 3

輸出

1

備注

對于100%的數(shù)據(jù)，1<=N<=100，0<=M<=4500。數(shù)據(jù)保證M對關(guān)系不出現(xiàn)矛盾。sjynoi 思路：
floyd傳遞閉包，如果所有人除了自己都在都在自己的前或后，就一定不并排 1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<algorithm> 6 #include<vector> 7 using namespace std; 8 const int maxn = 105; 9 const int maxint = 100000000; 10 int n,m,g[maxn][maxn],tg[maxn][maxn],ans,nowans; 11 void input(){ 12 cin>>n>>m; 13 int u,v; 14 for(int i = 1;i <= m;i++){ 15 cin>>u>>v; 16 g[u][v] = 1; 17 } 18 } 19 void build(){ 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(k != i && k != j && i != j) g[i][j] = g[i][j] || (g[i][k] && g[k][j]); 24 } 25 } 26 } 27 for(int i = 1;i <= n;i++){ 28 nowans = 0; 29 for(int j = 1;j <= n;j++){ 30 if(g[i][j]) nowans++; 31 if(g[j][i]) nowans++; 32 } 33 if(nowans == n-1) ans++; 34 } 35 cout<<ans<<endl; 36 } 37 int main(){ 38 input(); 39 build(); 40 } View Code

?

Tyvj 1139 向遠方奔跑（APIO 2009 搶掠計劃）

描述

在唐山一中，吃飯是一件很令人頭疼的事情，因為你不可能每次都站在隊伍前面買飯，所以，你最需要做的一件事就是——跑飯。而跑飯的道路是無比艱難的，因為路是單向的（你要非說成是雙向的我也沒法，前提是你可以逆著2000+個狂熱的跑飯群眾而行），所以要合理選擇路線。并且，在抵達你的目的地——板面館之前，你需要先買一些干糧，比如燒餅之類的。現(xiàn)在給你每個干食商店的位置和干食喜愛度，請你設(shè)計一個跑飯方案使得在到達板面館之前能得到盡可能多的干食喜愛度。

輸入格式

第一行包含兩個整數(shù)N、M。N表示食品商店的個數(shù)，M表示道路條數(shù)。接下來M行，每行兩個整數(shù)，這兩個整數(shù)都在1到N之間，第i+1行的兩個整數(shù)表示第i條道?路的起點和終點的食品商店編號。接下來N行，每行一個整數(shù)，按順序表示每個食品商店處的干食喜愛度。接下來一行包含兩個整數(shù)S、P，S表示學(xué)校的編號，也就是出發(fā)地點。P表示板面館數(shù)目。接下來的一行中有P個整數(shù)，表示P個賣板面的食品商店的編號。

輸出格式

輸出一個整數(shù)，表示到達板面館之前能得到的最多的干食喜愛度。

測試樣例1

輸入

6 7?
1 2?
2 3?
3 5?
2 4?
4 1?
2 6?
6 5?
10?
12?
8?
16?
1?
5?
1 4?
4 3 5 6

輸出

47

備注

40%的數(shù)據(jù)n,m<=300???100%的數(shù)據(jù)n,m<=3000?

思路：

1、分析路可以重復(fù)走，想到強連通分量，如果強連通分量里面有一個點被訪問，那么整個強連通分量都要被訪問，否則答案偏小，于是先tarjan再縮點

2、縮點之后，整個圖由一個有向有環(huán)圖變?yōu)橐粋€有向無環(huán)圖，于是spfa處理,然后就AC了（機智如我╮(╯3╰)╭）

代碼：

1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<vector> 6 #include<algorithm> 7 #include<queue> 8 #include<stack> 9 #define maxn 3005 10 #define maxint ~0U>>1 11 using namespace std; 12 stack<int> sta; 13 vector<int> comp[maxn]; 14 int incomp[maxn],instack[maxn],dfn[maxn],low[maxn]; 15 int index,cnum; 16 int n,m,q,d[maxn],rice[maxn],noodle[maxn],v[maxn],s,p,ans; 17 vector<int> g[maxn],nowg[maxn]; 18 int nowrice[maxn],nownoodle[maxn],nows; 19 void input(){ 20 cin>>n>>m; 21 int u,v; 22 for(int i = 1;i <= m;i++){ 23 scanf("%d%d",&u,&v); 24 g[u].push_back(v); 25 26 } 27 for(int i = 1;i <= n;i++){ 28 scanf("%d",&rice[i]); 29 } 30 cin>>s>>p; 31 int nnow; 32 for(int i = 1;i <= p;i++){ 33 scanf("%d",&nnow); 34 noodle[nnow] = 1; 35 } 36 } 37 void tarjan(int u){ 38 instack[u] = 2; 39 dfn[u] = low[u] = ++index; 40 sta.push(u); 41 for(int i = 0;i < g[u].size();i++){ 42 int j = g[u][i]; 43 if(!dfn[j]){ 44 tarjan(j); 45 low[u] = min(low[u],low[j]); 46 }else if(instack[j] == 2){ 47 low[u] = min(low[u],dfn[j]); 48 } 49 } 50 if(dfn[u] == low[u]){ 51 ++cnum; 52 while(!sta.empty()){ 53 int t = sta.top(); 54 sta.pop(); 55 instack[t] = 1; 56 incomp[t] = cnum; 57 comp[cnum].push_back(t); 58 if(t == u){ 59 break; 60 } 61 } 62 } 63 } 64 void work(){ 65 for(int i = 1;i <= n;i++){ 66 if(!dfn[i]) tarjan(i); 67 } 68 int u,v,newu,newv; 69 for(int i = 1;i <= n;i++){ 70 u = i; 71 newu = incomp[u]; 72 nowrice[newu] += rice[u]; 73 if(noodle[u]) nownoodle[newu] = 1; 74 if(u == s) nows = newu; 75 for(int j = 0;j < g[u].size();j++){ 76 v = g[u][j]; 77 newv = incomp[v]; 78 if(newu == newv) continue; 79 nowg[newu].push_back(newv); 80 } 81 } 82 } 83 void spfa(){ 84 queue<int> q; 85 d[nows] = nowrice[nows]; 86 v[nows] = 1; 87 q.push(nows); 88 int xx,dd,to,wei; 89 while(!q.empty()){ 90 xx = q.front(); 91 dd = d[xx]; 92 q.pop(); 93 v[xx] = 0; 94 if(nownoodle[xx]) ans = max(ans,dd); 95 for(int i = 0;i < nowg[xx].size();i++){ 96 to = nowg[xx][i]; 97 wei = nowrice[to]; 98 if(dd + wei > d[to]){ 99 d[to] = dd + wei; 100 if(!v[to]){ 101 v[to] = 1; 102 q.push(to); 103 } 104 } 105 } 106 } 107 cout<<ans; 108 } 109 int main(){ 110 input(); 111 work(); 112 spfa(); 113 return 0; 114 } View Code

Tyvj?1202 數(shù)數(shù)食物鏈

描述

TsyD學(xué)習(xí)了生物的生態(tài)環(huán)境那一張后，老師留了一項作業(yè)，就是給一張食物網(wǎng)，求所有食物鏈的總數(shù)。（從最低營養(yǎng)級生物（它不能吃任何其他的生物）開始到最高營養(yǎng)級（它不能被任何其他生物吃）?叫做一條食物鏈）
輸入保證所有的生物之間都有直接或間接的生存關(guān)系

輸入格式

第一行?N,M?分別表示有N（N<=50000）個生物，M(M<=100000)個吃的關(guān)系
接下來M行?每行有兩個值a，b?分別?表示b吃a?（編號從1開始）

輸出格式

食物鏈的總數(shù)?MOD?11129?的值

測試樣例1

輸入

3 3?
1 2?
2 3?
1 3

輸出

2

備注

樣例解釋：
兩條食物鏈分別為?1->3
?1->2->3 思路： 拓撲排序找到入度為0的點，然后dp 代碼： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int out[50010],G[50010][310],in[50010];//出度，鄰接表 從1開始 6 int n,m; 7 int f[50010];//f[k]表示k到頂端共有多少條鏈 8 void dfs(int k) 9 { 10 if(out[k]==0)//頂端 11 { 12 f[k]=1; 13 return ; 14 } 15 for(int i=1;i<=out[k];i++) 16 { 17 if(f[G[k][i]]==0) dfs(G[k][i]); 18 f[k]=(f[k]+f[G[k][i]])%11129; 19 } 20 } 21 int main() 22 { 23 while(scanf("%d%d",&n,&m)==2) 24 { 25 memset(out,0,sizeof(out)); 26 memset(G,0,sizeof(G)); 27 memset(f,0,sizeof(f)); 28 memset(in,0,sizeof(in)); 29 while(m--) 30 { 31 int x,y;scanf("%d%d",&x,&y); 32 out[x]++;in[y]++; 33 G[x][out[x]]=y; 34 } 35 int cnt=0; 36 for(int i=1;i<=n;i++) 37 { 38 if(in[i]==0) 39 { 40 dfs(i); 41 cnt=(cnt+f[i])%11129; 42 } 43 } 44 printf("%d",cnt); 45 } 46 return 0; 47 } View Code

Wikioi 3731 尋找道路

題目描述?Description

在有向圖G中，每條邊的長度均為1，現(xiàn)給定起點和終點，請你在圖中找一條從起點到終點的路徑，該路徑滿足以下條件：

1．路徑上的所有點的出邊所指向的點都直接或間接與終點連通。

2．在滿足條件1的情況下使路徑最短。

注意：圖G中可能存在重邊和自環(huán)，題目保證終點沒有出邊。

請你輸出符合條件的路徑的長度。

?

輸入描述?Input Description

第一行有兩個用一個空格隔開的整數(shù)n和m，表示圖有n個點和m條邊。

接下來的m行每行2個整數(shù)x、y，之間用一個空格隔開，表示有一條邊從點x指向點y。

最后一行有兩個用一個空格隔開的整數(shù)s、t，表示起點為s，終點為t。

?

輸出描述?Output Description

輸出文件名為road.out。

輸出只有一行，包含一個整數(shù)，表示滿足題目描述的最短路徑的長度。如果這樣的路徑不存在，輸出-1。

樣例輸入?Sample Input

road.in	road.out
3?2 1?2 2?1 1?3	－1

樣例輸出?Sample Output

road.in	road.out
6?6 1?2 1?3 2?6 2?5 4?5 3?4 1?5	3

數(shù)據(jù)范圍及提示?Data Size & Hint

對于30%的數(shù)據(jù)，0<?n?≤10，0<?m?≤20；

對于60%的數(shù)據(jù)，0<?n?≤100，0<?m?≤2000；

對于100%的數(shù)據(jù)，0<?n?≤10,000，0<?m?≤200,000，0<?x,y,s,t≤n，x≠t。

思路：

分析問題，做的最短路中的點既能從起點出發(fā)，又能從終點回來，所以先預(yù)處理，有兩種方式，可以先在起點進行一遍bfs，把在沒到終點前就沒有出邊的點標記下，然后再沿著反圖進行一遍bfs，或者可以直接從終點出發(fā)在反圖進行一遍bfs，把沒涉及到的點標出來，然后再在反圖bfs，最后最短路

代碼：

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 7 using namespace std; 8 9 const int maxn = 200005,maxnum = 100000; 10 int dist[maxn],jud[maxn],q[maxn],start[maxn],tnum[maxn],fjud[maxn],cuter[maxn],n,m,x,t,ans,num = 0; 11 12 struct star{ 13 int next; 14 int to; 15 int p; 16 }; 17 star edge[maxn]; 18 19 void dfs(int node){ 20 int head = 1,tail = 1,bq[maxn]; 21 fjud[node] = 0; 22 bq[1] = node; 23 while(head <= tail){ 24 int now = bq[head]; 25 for(int i = start[now];i != -1;i = edge[i].next){ 26 if(fjud[edge[i].to]){ 27 tail = (tail + 1) % maxn; 28 bq[tail] = edge[i].to; 29 fjud[edge[i].to] = 0; 30 } 31 } 32 head = (head + 1) % maxn; 33 } 34 } 35 36 void dfs1(int node){ 37 int head = 1,tail = 1,bq[maxn]; 38 cuter[node] = 0; 39 bq[1] = node; 40 while(head <= tail){ 41 int now = bq[head]; 42 for(int i = start[now];i != -1;i = edge[i].next){ 43 if(cuter[edge[i].to]){ 44 bq[tail] = edge[i].to; 45 cuter[edge[i].to] = 0; 46 } 47 } 48 head = (head + 1) % maxn; 49 } 50 } 51 52 int spfa(int u,int v){ 53 dist[u] = jud[u] = 0; 54 q[1] = u; 55 int head = 1,tail = 1; 56 while(head <= tail){ 57 int now = q[head]; 58 for(int i = start[now];i != -1;i = edge[i].next){ 59 60 if(dist[edge[i].to] > dist[now] + edge[i].p && cuter[edge[i].to]){ 61 dist[edge[i].to] = dist[now] + edge[i].p; 62 if(jud[edge[i].to]){ 63 tail = (tail + 1) % maxn; 64 q[tail] = edge[i].to; 65 jud[edge[i].to] = 0; 66 } 67 } 68 } 69 70 head = (head + 1) % maxn; 71 jud[now] = 1; 72 } 73 if(dist[v] == 100000) return -1; 74 return dist[v]; 75 } 76 77 int main(){ 78 cin>>n>>m; 79 int u,v,p; 80 for(int i = 1;i <= n;i++){ 81 start[i] = -1; 82 dist[i] = maxnum; 83 jud[i] = 1; 84 fjud[i] = 1; 85 cuter[i] = 1; 86 tnum[i] = 0; 87 88 } 89 int cnt = 1; 90 for(int i = 1;i<= m;i++){ 91 cin>>u>>v; 92 swap(u,v); 93 edge[i].p = 1; 94 edge[i].to = v; 95 edge[i].next=start[u]; 96 cnt++; 97 start[u] = cnt - 1; 98 tnum[u]++; 99 } 100 cin>>x>>t; 101 dfs(t); 102 for(int i = 1;i <= n;i++) if(fjud[i]) dfs1(i); 103 cuter[x]= cuter[t] = 1; 104 ans = spfa(t,x); 105 cout<<ans; 106 return 0; 107 } View Code

?Wikioi 1009 產(chǎn)生數(shù)

?

題目描述?Description

　　給出一個整數(shù) n（n<10^30) 和 k 個變換規(guī)則（k<=15）。
　　規(guī)則：
　　　一位數(shù)可變換成另一個一位數(shù)：
　　　規(guī)則的右部不能為零。
　　例如：n=234。有規(guī)則（k＝2）：
　　　　2－> 5
　　　　3－> 6
　　上面的整數(shù) 234 經(jīng)過變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）:
　　　234
　　　534
　　　264
　　　564
　　共 4 種不同的產(chǎn)生數(shù)
問題：
　　給出一個整數(shù) n 和 k 個規(guī)則。
求出：
　　經(jīng)過任意次的變換（0次或多次），能產(chǎn)生出多少個不同整數(shù)。
　　僅要求輸出個數(shù)。

輸入描述?Input Description

鍵盤輸人，格式為：
?　　n k
?　　x1 y1
?　　x2 y2
?　　... ...
?　　xn yn

輸出描述?Output Description

?屏幕輸出，格式為：
　　一個整數(shù)（滿足條件的個數(shù)）

樣例輸入?Sample Input

　　 234 2
　 　2 5
?　　3 6

樣例輸出?Sample Output

4

思路：
floyd預(yù)處理一個數(shù)能變換成多少數(shù) 代碼： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cstdlib> 6 #include<algorithm> 7 8 using namespace std; 9 10 const int maxn = 1000; 11 char temp[maxn]; 12 int edge[maxn][maxn],cou[maxn],n,k,big[maxn]; 13 14 void init(){ 15 cin>>temp>>k; 16 n = strlen(temp); 17 for(int i = 0;i <= 9;i++){ 18 for(int j = 0;j <= 9;j++){ 19 if(i == j) edge[i][j] = 1; 20 else edge[i][j] = 0; 21 } 22 } 23 for(int i = 0;i < k;i++){ 24 int u,v; 25 cin>>u>>v; 26 edge[u][v] = 1; 27 } 28 big[0] = 1; 29 30 } 31 32 void fshort(){ 33 for(int k = 0;k <= 9;k++){ 34 for(int i = 0;i <= 9;i++){ 35 if(i != k){ 36 for(int j = 0;j <=9;j++) 37 if(j != i && j != k &&(edge[i][k] && edge[k][j])) edge[i][j] = 1; 38 39 } 40 } 41 } 42 for(int i = 0;i <= 9;i++) 43 for(int j = 0;j <= 9;j++) 44 cou[i] += edge[i][j]; 45 46 47 } 48 49 void mplus(){ 50 int ans = 1,a,b = 0; 51 for(int i = 0;i < n;i++){ 52 if(cou[temp[i] - 48]){ 53 a = cou[temp[i] - 48]; 54 for(int j = b;j >= 0;j--){ 55 big[j] *= a; 56 if(big[j] > 9){ 57 big[j + 1] += big[j] / 10; 58 big[j] = big[j] % 10; 59 if(j == b) b++; 60 } 61 } 62 } 63 64 } 65 for(int j = 0;j <= b;j++){ 66 if(big[j] > 9){ 67 big[j + 1] += big[j] / 10; 68 big[j] = big[j] % 10; 69 if(j == b) b++; 70 } 71 } 72 for(int r = b;r >= 0;r--)cout<<big[r]; 73 } 74 75 76 int main(){ 77 init(); 78 fshort(); 79 mplus(); 80 return 0; 81 } View Code

?

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

總結(jié)

以上是生活随笔為你收集整理的图论——连通图的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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