圖論——連通圖

Tyvj 2059 元芳看電影

描述

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

輸入格式

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

輸出格式

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

測試樣例1

輸入

3 2
1 2
1 3

輸出

1

備注

對于100%的數據，1<=N<=100，0<=M<=4500。數據保證M對關系不出現矛盾。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+個狂熱的跑飯群眾而行），所以要合理選擇路線。并且，在抵達你的目的地——板面館之前，你需要先買一些干糧，比如燒餅之類的。現在給你每個干食商店的位置和干食喜愛度，請你設計一個跑飯方案使得在到達板面館之前能得到盡可能多的干食喜愛度。

輸入格式

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

輸出格式

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

測試樣例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%的數據n,m<=300???100%的數據n,m<=3000?

思路：

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

2、縮點之后，整個圖由一個有向有環圖變為一個有向無環圖，于是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 數數食物鏈

描述

TsyD學習了生物的生態環境那一張后，老師留了一項作業，就是給一張食物網，求所有食物鏈的總數。（從最低營養級生物（它不能吃任何其他的生物）開始到最高營養級（它不能被任何其他生物吃）?叫做一條食物鏈）
輸入保證所有的生物之間都有直接或間接的生存關系

輸入格式

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

輸出格式

食物鏈的總數?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，現給定起點和終點，請你在圖中找一條從起點到終點的路徑，該路徑滿足以下條件：

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

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

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

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

輸入描述?Input Description

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

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

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

輸出描述?Output Description

輸出文件名為road.out。

輸出只有一行，包含一個整數，表示滿足題目描述的最短路徑的長度。如果這樣的路徑不存在，輸出-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

數據范圍及提示?Data Size & Hint

對于30%的數據，0<?n?≤10，0<?m?≤20；

對于60%的數據，0<?n?≤100，0<?m?≤2000；

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

思路：

分析問題，做的最短路中的點既能從起點出發，又能從終點回來，所以先預處理，有兩種方式，可以先在起點進行一遍bfs，把在沒到終點前就沒有出邊的點標記下，然后再沿著反圖進行一遍bfs，或者可以直接從終點出發在反圖進行一遍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 產生數

題目描述?Description

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

輸入描述?Input Description

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

輸出描述?Output Description

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

樣例輸入?Sample Input

　　 234 2
　　2 5
?　　3 6

樣例輸出?Sample Output

思路：
floyd預處理一個數能變換成多少數

代碼：

 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 }