图论——连通图

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 }

View Code