当前位置：

首页 > 未分类

所谓图论必做题小结

2010年09月03日 23:06   作者：Starvae   分类：未分类   77 views  

从没怎么写过贴代码的文章-_-~
网上找了个所谓的图论必做题，看了下，然后全部贴上来了，不断更新中哦~
欢迎找错，欢迎推荐好的图论题^_^

目录：

1.最短路问题.

2.生成树问题.

3.连通性，度数，拓扑问题.

4.2-SAT问题(另文).

5网络流问题(最大流，费用流).

6.匹配问题.

7.各种问题

最短路问题:

POJ 2449 Remmarguts’ Date(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2449

题意：经典问题：K短路

解法：dijkstra+A*(rec)，方法很多（这个不会 -_-|）

POJ 3013 - Big Christmas Tree(基础)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3013

题意：最简单最短路， need speed

解法：Dijkstra

POJ 3463 - Sightseeing(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3463

题意：最短路和比最短路大1的路的数量

解法：只要会求解次短路就OK了,但是这次短路不包括与最短路权值相同的路

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

#include<iostream>
using namespace std;
#include<queue>
#include<vector>
 
int dis[1100][2];
int num[1100][2];
struct ff
{
    int flag;//0zui  1 ci
    int val;//juli
    int node;//dian
    friend bool operator< (ff a,ff b)
    {
        return a.val > b.val;
    }
}temp,now;
 
priority_queue<ff>Q;
struct LINE
{
    int v;
    int valu;
}d;
vector<line>v[1100];
void DIJ(int s,int t)
{
    int i,j,k;
    while(!Q.empty())
        Q.top();
    memset(num,0,sizeof(num));
    dis[s][0]=0;
    num[s][0]=1;
    //dis[s][1]=0;
    now.flag=0;
    now.node=s;
    now.val=0;
    Q.push(now);
    while(!Q.empty())
    {
        now=Q.top();
        Q.pop();
        if(now.val>dis[now.node][now.flag])
            continue;
        for(i=0;i<v [now.node].size();i++)
        {
            int a=v[now.node][i].v;
            int b=v[now.node][i].valu;
            if(b+dis[now.node][now.flag]<dis[a][0] ||dis[a][0]==-1)
            {
                if(dis[a][0]!=-1)
                {
                    dis[a][1]=dis[a][0];
                    num[a][1]=num[a][0];
                    temp.flag=1;
                    temp.node=a;
                    temp.val=dis[a][1];
                    Q.push(temp);
                }
                dis[a][0]=b+dis[now.node][now.flag];
                num[a][0]=num[now.node][now.flag];
                temp.flag=0;
                temp.node=a;
                temp.val=dis[a][0];
                Q.push(temp);
            }
            else if(b+dis[now.node][now.flag]==dis[a][0])
            {
                num[a][0]+=num[now.node][now.flag];
            }
            else if(b+dis[now.node][now.flag]<dis[a][1]||dis[a][1]==-1)
            {
                dis[a][1]=dis[now.node][now.flag]+b;
                num[a][1]=num[now.node][now.flag];
                temp.flag=1;
                temp.node=a;
                temp.val=dis[a][1];
                Q.push(temp);
            }
            else if(b+dis[now.node][now.flag]==dis[a][1])
            {
                num[a][1]+=num[now.node][now.flag];
            }
        }
    }
    return ;
}
 
 
int main()
{
    int ca;
    int i,j,k;
    int n,m;
    int s,t;
    int a;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)
            v[i].clear();
        memset(dis,-1,sizeof(dis));
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&a,&d.v,&d.valu);
            v[a].push_back(d);
        }
        scanf("%d %d",&s,&t);
        DIJ(s,t);
        int ans=num[t][0];
        if(dis[t][1]-1==dis[t][0])
            ans+=num[t][1];
        printf("%d\n",ans);
    }
    return 0;
}

POJ 3613 - Cow Relays(难)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3613

题意：在一个无向图中，给你起点终点，求经过N条边的最短路

解法：矩阵乘法计算经过的点数，并随时更新最短路，类floyd

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include<iostream>
#include<string .h>
#include<algorithm>
using namespace std;
#define INF 0x3fffffff
int n,m;
int s,t;
int map[210][210];
int hash[1100];
int make(int a)
{
	if(hash[a] != 0 )
		return hash[a];
	hash[a] = ++m;
	return hash[a];
}
int ans[210][210];
int temp[210][210];
void floyd()
{
	int i,j,k;
	n -- ;
	for(i = 1;i < = m;i ++)
	{
		for(j = 1;j <= m; j++)
			ans[i][j] = map[i][j];
	}
	while(n!=0)
	{
		if(n&1)
		{
			for(i=1;i<=m;i++)
			{
				for(j=1;j<=m;j++)
				{
					temp[i][j]= INF;
					for(k=1;k<=m;k++)
					{
						int z = ans[i][k]+map[k][j];
					temp[i][j]= min(temp[i][j],z);
					}
				}
			}
			for(i=1;i<=m;i++)
			{
				for(j=1;j<=m;j++)
				{
					ans[i][j]= temp[i][j];
				}
			}
		}
 
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=m;j++)
			{
				temp[i][j] = INF;
				for(k=1;k<=m;k++)
				{
					int z = map[i][k]+map[k][j];
					temp[i][j]= min(temp[i][j],z);
				}
			}
		}
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=m;j++)
				map[i][j] = temp[i][j];
		}
		n = n>>1;
	}
 
}
 
int main()
{
	int i,j,k;
	int a,b,c;
	while(scanf("%d %d %d %d",&n,&k,&s,&t)!=EOF)
	{
		memset(hash,0,sizeof(hash));
		m = 0;
		for(i=0;i< =200;i++)
			for(j=0;j<=200;j++)
				map[i][j] =INF;
		for(i=0;i<k;i++)
		{
			scanf("%d %d %d",&a,&b,&c);
			b = make (b);
			c = make (c);
			map[b][c] = map[c][b] = a;
		}
 
		floyd();
		printf("%d\n",ans[make(s)][make(t)]);
	}
	return 0;
}

POJ 3621 - Sightseeing Cows(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3621

题意：求一个环路，欢乐值 / 总路径最大

解法：二分答案 + SPFA (G++ 一直WA，而且不止我一个..)

类似于01分数规划，先二分答案，然后修改边权，判断是否有负环存在，诺存在则答案OK,然后寻找最大的答案。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

#include <cstdlib> 
#include <cctype> 
#include <cstring> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <map> 
#include <set> 
#include <queue> 
#include <stack> 
using namespace std; 
 
#define eps 1e-4
 
struct EDGE
{
	int v;
	double dis;
	int next;
}E[6000];
 
struct ff
{
	int u;
	int v;
	int dis;
}f[5100];
int val[1100];
int n,m;
int head[1100];
int num;
 
void addedge(int u,int v,double dis)
{
	E[num].dis = dis;
	E[num].v = v;
	E[num].next = head[u];
	head[u] = num++;
}
void init()
{
	memset(head,-1,sizeof(head));
	num = 0;
}
void build(double mid)
{
	init();
	for(int i =0;i<m ;i++)
	{
		addedge(f[i].u,f[i].v,f[i].dis*mid - val[f[i].u]);
	}
}
 
double dis[1100];
int Q[1000000];
bool spfa()
{
	int i,j,k;
	for(i=1;i<=n;i++)
		dis[i] = 100000000.0;
//	queue<int>Q;
	int le = 0;
	int ri = 1;
//	Q.push(1);
	Q[le] = 1;
	dis[1] = 0;
	int du[1100] = {0};
	int hash[1100] = {0};
	while(le<ri )
	{
		//int u = Q.front();
		//Q.pop();
		int u = Q[le++];
		hash[u] = 0;
		for(i=head[u]; i != -1; i =E[i].next)
		{
			int v = E[i].v;
			if(dis[v] > dis[u] + E[i].dis)
			{
				dis[v] = dis[u] + E[i].dis;
				if(hash[v] == 0)
				{
				//	Q.push(v);
					Q[ri++] = v;
 
					hash[v] = 1;
				}
				du[v] ++ ;
				if(du[v] == n)
					return true;
			}
		}
	}
	return false;
}
 
int main()
{
	int i,j,k;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i< =n;i++)
			scanf("%d",&val[i]);
		for(i=0;i<m;i++)
			scanf("%d %d %d",&f[i].u,&f[i].v,&f[i].dis);
		double le = 0;
		double ri = 10000000;
		double ans=-1,mid;
 
		while(le + eps < ri)
		{
			mid = (le + ri)/2.0;
			build(mid);
			if(spfa())
			{
				ans = mid;
				le = mid +eps ;
			}
			else
				ri = mid-eps ;
		}
		if(ans&lt;0)
			printf("0\n");
		else
			printf("%.2lf\n",ans);
	}
	return 0;
}

POJ 3635 - full tank?(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3635

题意：最短路变形,加油站的问题，起点终点使得所用费用最少

解法：dis[lim][n]的广搜。但要注意剪枝，可以用G++交，相差很多~

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

#include <cstdlib> 
#include <cctype> 
#include <cstring> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <map> 
#include <set> 
#include <queue> 
#include <stack> 
using namespace std; 
 
 
struct FF
{
	int a;
	int b;
	int val;
	friend bool operator< (FF a,FF b)
	{
		return a.val > b.val;
	}
}now,temp;
 
priority_queue<ff>Q;
int  dis[110][1100];
int n,m;
struct EDGE
{
	int next;
	int v;
	int dis;
}E[21000];
int head[1100];
int num;
int val[1100];
 
int work(int lim,int s,int t)
{
	int i,j,k;
	memset(dis,-1,sizeof(dis));
	while(!Q.empty())
		Q.pop();
	dis[0][s] = 0;
	dis[1][s] = val[s];
	now.a = 1;
	now.b =s;
	now.val = val[s];
	Q.push(now);
	while(!Q.empty())
	{
		now = Q.top();
		Q.pop();
		if(now.b == t)
			break;
		if(dis[now.a][now.b]!=now.val )
			continue;
		int u = now.b;
		for(i=head[u];i!=-1;i=E[i].next)
		{
			if(E[i].dis < = now.a)
			{
				temp.a = now.a-E[i].dis;
				temp.b = E[i].v;
				temp.val = now.val;
				if(dis[temp.a][temp.b] ==-1 || dis[temp.a][temp.b]>temp.val)
				{
					dis[temp.a][temp.b] = temp.val;
					Q.push(temp);
				}
			}
		}
		i = now.a+1;
		if(i< =lim &&dis[i][u]==-1 || dis[i][u] > now.val + val[u])
		{
			dis[i][u] = now.val + val[u];
			temp.a = i;
			temp.b = u;
			temp.val = dis[i][u];
			Q.push(temp);
		}
	}
	return dis[0][t];
}
 
void addedge(int u,int v,int c)
{
	E[num].v = v;
	E[num].dis = c;
	E[num].next = head[u];
	head[u] = num++;
	E[num].v = u;
	E[num].dis = c;
	E[num].next = head[v];
	head[v] = num++;
}
void init()
{
	memset(head,-1,sizeof(head));
	num = 0;
}
int main()
{
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(int i=0;i<n ;i++)
			scanf("%d",&val[i]);
		init();
		int a,b,c;
		for(int i=0;i<m;i++)
		{
			scanf("%d %d %d",&a,&b,&c);
			addedge(a,b,c);
		}
		int p;
		scanf("%d",&p);
		while(p--)
		{
			scanf("%d %d %d",&a,&b,&c);
			int ans = work(a,b,c);
			if(ans == -1)
				printf("impossible\n");
			else
				printf("%d\n",ans);
		}
	}
	return 0;
}

生成树问题：

POJ 1639 – Picnic Planning(较难)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1639

题意：顶点度数有限制的最小生成树 生成树的一个小变化

解法：贪心 + prim/kruskal 先去掉v0，然后求各个连通分量的最小生成树，然后用最小的代价将其与v0连接，如果有m个连通分量，那么就是m度最小生成树
现在对于该生成树设定一个best[]，best[i]表示有一条不在生成树上的边连接v0与vi，并且所形成的环的边中的不包括与v0连接的边中的最大权值，然后寻找这个best[]最小的，并更新生成树变成m+1度最小生成树，最后变为K度最小生成树

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string .h>
#include</string><string>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
 
#define MAXM 1000000
#define MAXN 1100
#define INF 0x3fffffff
class K_Tree {
public:
	struct EDGE {
		int v;
		int dis;
		int next;
	} E[MAXM];
	int head[MAXN];
	int tree[MAXN];
	int NE;//边数
	int NV;//点数
	int sr;//需要收到度限制的根
	int pre[MAXN], dis[MAXN];
	int father[MAXN];
	int best[MAXN];
	int vis[MAXN];
 
	void addedge(int u, int v, int c) {
		//无向边
		E[NE].dis = c;E[NE].v = v;
		E[NE].next = head[u];head[u] = NE++;
		E[NE].dis = c;E[NE].v = u;
		E[NE].next = head[v];head[v] = NE++;
	}
	void addtree(int u, int v, int c) {
		//无向边
		//	printf("  tree  %d %d  %d\n",u,v,c);
		E[NE].dis = c;E[NE].v = v;
		E[NE].next = tree[u];tree[u] = NE++;
		E[NE].dis = c;	E[NE].v = u;
		E[NE].next = tree[v];tree[v] = NE++;
	}
	void init(int n) {
		NV = n;	NE = 0;
		memset(head, -1, sizeof(int) * NV);
		memset(tree, -1, sizeof(int) * NV);
	}
	void dfs(int s) {
		for (int i = tree[s]; i != -1; i = E[i].next) {
			int v = E[i].v;
			if (s == v || vis[v] == -2)
				continue;
			father[v] = s;
			vis[v] = -2;
			dfs(v);
		}
	}
	int prim(int s) {
		int i, M, key;
		int sum = 0;
		for (i = head[s]; i != -1; i = E[i].next) {
			int v = E[i].v;
			dis[v] = min(dis[v], E[i].dis);
			pre[v] = s;
		}
		vis[s] = s;
		while (1) {
			M = INF; key = -1;
			for (i = 0; i < NV; i++)
				if (vis[i] == -1 && dis[i] < M) {
					key = i;
					M = dis[i];
				}
			if (key == -1)
				break;
			vis[key] = s;
			addtree(pre[key], key, dis[key]);
			sum += dis[key];
			for (i = head[key]; i != -1; i = E[i].next) {
				int v = E[i].v;
				if (vis[v] == -1 && dis[v] > E[i].dis) {
					dis[v] = E[i].dis;
					pre[v] = key;
				}
			}
		}
		M = INF;
		int root = -1;
		for (i = head[sr]; i != -1; i = E[i].next) {
			int v = E[i].v;
			if (vis[v] == s && M > E[i].dis) {
				M = E[i].dis;
				root = v;
			}
		}
		addtree(sr, root, M);
		father[root] = sr;
		dfs(root);
		return sum + M;
 
	}
	void Fbest(int s) {
		if (father[s] == -1 || father[s] == sr)
			best[s] = -INF;
		else {
			best[s] = best[father[s]];
			pre[s] = pre[father[s]];
		}
		for (int i = tree[s]; i != -1; i = E[i].next) {
			if (E[i].v == father[s]) {
				if (best[s] < E[i].dis) {
					best[s] = E[i].dis;
					pre[s] = i;
					break;
				}
			}
		}
		for (int i = tree[s]; i != -1; i = E[i].next) {
 
			int v = E[i].v;
			if (E[i].dis == INF)
				continue;
			if (v == father[s]) {
				continue;
			} else {
				father[v] = s;
				Fbest(v);
			}
		}
	}
	void BuildBest() {
		int i;
		for (i = 0; i < NV; i++)
			best[i] = -INF;
		father[0] = -1;
		Fbest(0);
	}
	void Slove(int K) {
		memset(vis, -1, sizeof(int) * NV);
		memset(pre, 0, sizeof(int) * NV);
		for (int i = 0; i < NV; i++)
			dis[i] = INF;
		int m = 0;
		int mst = 0;//生成树总值
		sr = 0;//规定sr的度最大为K
		vis[sr] = 0;
		father[sr] = -1;
		for (int i = 0; i < NV; i++) {
			if (vis[i] == -1) {
				m++;
				mst += prim(i);
			}
		}
 
		//m度生成树已经建好
 
		int M, change;
		for (int i = m + 1; i <= K; i++) {
			BuildBest();
 
			M = INF;
			change = -1;
			for (int j = head[sr]; j != -1; j = E[j].next) {
				int v = E[j].v;
				if (father[v] == sr)
					continue;
				int tmp = E[j].dis - best[v];
				if (tmp < M) {
					M = tmp;
					change = j;
				}
			}
			if (M >= 0)
				break;//表示当前状态是度数小于等于K时的最小值
			mst += M;
			int v = E[change].v;
			addtree(sr, v, E[change].dis);
			E[change].dis = E[change ^ 1].dis = INF;
			E[pre[v]].dis = E[pre[v] ^ 1].dis = INF;
		}
		printf("Total miles driven: %d\n", mst);
	}
 
} G;
int idx;
string s[200];
int F(string &p) {
	for (int i = 0; i < idx; i++)
		if (s[i] == p)
			return i;
	s[idx++] = p;
	return idx - 1;
}
int map[31][31];
int main() {
 
//	freopen("in.in","r",stdin);
	int n, m;
	int i;
	string temp = "Park";
	string a, b;
	int x, y, c;
	while (scanf("%d %d", &n, &m) != EOF) {
		idx = 0;
		F(temp);
		memset(map, -1, sizeof(map));
		G.init(n * 2);
		for (i = 0; i < n; i++) {
			cin >> a >> b >> c;
			x = F(a);
			y = F(b);
			//	G.addedge(x, y, c);
			if (map[x][y] == -1 || map[x][y] > c)
				map[x][y] = map[y][x] = c;
			//	printf("  %d %d  %d\n",x,y,c);
		}
		G.NV = idx;
		for (i = 0; i < idx; i++) {
			for (int j = i + 1; j < idx; j++)
				if (map[i][j] != -1) {
					G.addedge(i, j, map[i][j]);
				}
		}
		scanf("%d", &m);
		G.Slove(m);
	}
	return 0;
}

POJ 1679 – The Unique MST(基础)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1679

题意：判断MST是否唯一

解法：prim，做prim的时候找最小值边时，加一个cnt[]表示当前已经形成的树中的点与i连接的点的最小值边有cnt[i]条，当扩展一个点时，如果其cnt[i]大于1则MST不唯一；事实证明上面的方法是错误的，看一下这组数据就知道了，这个题的数据弱了，
4 4
1 2 1
2 3 5
3 4 2
4 1 5
正确的做法应该是先求最小生成树，然后预处理出树上的点经过各个边之间的最小值，然后枚举边，判断，相当于求了一棵次小生成树~

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include<iostream>
using namespace std;
#include<queue>
#include<vector>
 
struct EDGE
{
	int v;
	int num;
	int dis;
}now,temp;
#define INF 0x3fffffff
vector<edge>E[110];
int n,m;
 
int cnt[110];//cishu 
int mm[110];//zuixiao
int hash[110];//hash
 
void work()
{
	int i,j,k;
	for(i=1;i< =n;i++)
	{
		mm[i] = INF;
		cnt[i] = 1;
	}
	for(i=0;i<E[1].size();i++)
		mm[E[1][i].v] = E[1][i].dis;
	int flag = 0;
	int ans = 0;
 
	memset(hash,0,sizeof(hash));
	hash[1] = 1;
	while(1)
	{
		int ok = -1;
		int mmin = INF;
		for(i=1;i<=n;i++)
		{
			if(hash[i] ==0 && mm[i] < mmin)
			{
				mmin = mm[i];
				ok = i;
			}
		}
		if(ok == -1)
			break;
		if( cnt[ok] != 1 )
		{
			flag = 1;
			break;
		}
		ans += mmin;
		//printf("ans  %d\n",ans);
		hash[ok] = 1;
		for(i=0;i<E[ok].size();i++)
		{
			if(mm[E[ok][i].v] > E[ok][i].dis )
			{
				mm[E[ok][i].v] = E[ok][i].dis;
				cnt[E[ok][i].v] = 1;
			}
			else if(mm[E[ok][i].v] == E[ok][i].dis )
			{
				cnt[E[ok][i].v] ++;
			}
		}
	}
	if(flag )
		printf("Not Unique!\n");
	else
		printf("%d\n",ans);
}
 
void init()
{
	int i,j,k;
	scanf("%d %d",&n,&m);
	for(i=1;i< =n;i++)
		E[i].clear();
	int a,b,c;
	for(i=0;i<m;i++)
	{
		scanf("%d %d %d",&a,&b,&c);
	//	now.num = i;
		now.dis = c;
		now.v = b;
		E[a].push_back(now);
		now.v = a;
		E[b].push_back(now);
	}
}
 
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		init();
		work();
	}
	return 0;
}

POJ 2728 – Desert King(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2728

题意：最优比率生成树

解法：最优比率生成树，01分数规划的论文里面有讲，最直白的方法就是二分，当然牛逼一点的迭代更帅~

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

#include<iostream>
using namespace std;
#include<stdio .h>
#include<math .h>
struct ff
{
	double len;
	double val;
}f[1001][1001];
double map[1001][1001];
int n;
struct V
{
	double x;
	double y;
	double hi;
}v[1001];
double xx,yy;
void prim()
{
	double mmin;
	double va[1001]={0},m[1001];
	int qian[1001]={0};
	int i,j;
	for(i=1;i< =n;i++)
	{
		//va[i]=0;
		m[i]=map[1][i];
		qian[i]=1;
	}
	va[1]=1;
 
	int haha;
	int ne=1;
	while(1)
	{
		mmin=1000000000;
		haha=-1;
		for(i=1;i<=n;i++)
		{
			if(va[i]==0 && m[i]<=mmin)
			{
				haha=i;
				mmin=m[i];
			}
		}
		if(haha==-1)
			break;
 
		xx+=f[qian[haha]][haha].len;
		yy+=f[qian[haha]][haha].val;
		va[haha]=-1;
		for(i=1;i<=n;i++)
		{
			if(va[i]==0 && m[i]>map[haha][i])
			{
				m[i]=map[haha][i];
				qian[i]=haha;
			}
		}
	}
	//printf("  %lf \n",sum);
	//return sum;
	return ;
 
}
int main()
{
	int i,j;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		for(i=1;i< =n;i++)
			scanf("%lf %lf %lf",&v[i].x,&v[i].y,&v[i].hi);
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
			{
				f[j][i].len=f[i][j].len=sqrt( (v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y) );
				f[j][i].val=f[i][j].val=fabs(v[i].hi-v[j].hi);
			}
		double mid=0;
		double mmid=0;
		while(1)
		{
		//	mid=(l+r)/2.0;
			for(i=1;i<=n;i++)
			{
				//map[i][i]=1000000000;
				for(j=i+1;j<=n;j++)
					map[j][i]=map[i][j]=f[i][j].val-f[i][j].len*mid;
			}
			xx=0;
			yy=0;
			prim();
		//	printf("%lf %lf\n",xx,yy);
			mmid=yy/xx;
		//	printf("%lf\n",mmid);
			if(fabs(mmid- mid)&lt;0.001)
				break;
			else
				mid=mmid;
		}
		printf("%.3lf\n",mid);
	}
	return 0;
}

POJ 3164 – Command Network(难)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3164

题意：最小树形图

解法：最小树形图，刘朱算法，比较单一的一个算法，

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

/*
最小树形图 N^3 算法
*/
#include<iostream>
using namespace std;
#include<queue>
#include<math .h>
#define MAX 9999999999
#define M 128 //设定点的数量
double map[M][M];//保存图
int N;//N个结点
double ans;//记录树数值
 
bool vis[M]; 
void dfs(int v)
{
	int i;
	vis[v]=true;
	for(i=2;i< =N;++i)
		if((!vis[i])&&map[v][i]!=MAX)
			dfs(i); 
}
bool possible()
{//与dfs()连用，判断是不是连通图~
	int i;
	memset(vis,0,sizeof(vis));
	dfs(1);
	for(i=2;i<=N;++i)
		if(!vis[i])
			return false;
	return true;
}
 
int pre[M];
bool del[M];
void slove()
{
	int num=N;
	memset(del,0,sizeof(del));
	while(1)
	{
		int i,j;
		for(i=2;i<=N;i++)
		{
			if(del[i])continue;
			pre[i]=i;
			map[i][i]=MAX;
			for(j=1;j<=N;j++)
			{
				if(del[j])continue;
				if(map[j][i]<map[pre[i]][i])
					pre[i]=j;
			}
		}
		for(i=2;i<=N;i++)
		{
			if(del[i])continue;
			int j=i;
			memset(vis,0,sizeof(vis));
			while(!vis[j] && j!=1)
			{
				vis[j]=true;
				j=pre[j];
			}
			if(j==1)continue;
			i=j;
			ans+=map[pre[i]][i];
			for(j=pre[i];j!=i;j=pre[j])
			{
				ans+=map[pre[j]][j];
				del[j]=true;
			}
			for(j=1;j<=N;j++)
			{
				if(del[j])continue;
				if(map[j][i]!=MAX)
					map[j][i]-=map[pre[i]][i];
			}
			for(j=pre[i];j!=i;j=pre[j])
			{
				for(int k=1;k<=N;k++)
				{
					if(del[k])continue;
					if(map[i][k]>map[j][k])
						map[i][k]=map[j][k];
					if(map[k][j]!=MAX)
					{
						if(map[k][i] > map[k][j]-map[pre[j]][j])
							map[k][i] = map[k][j]-map[pre[j]][j];
					}
				}
			}
			for(j=pre[i];j!=i;j=pre[j])
			{
				del[j]=true;
			}
			break;
		}
		if(i>N)
		{
			for(int i=2;i< =N;i++)
			{
				if(del[i])continue;
				ans+=map[pre[i]][i];
			}
			break;
		}
	}
}
struct ff
{
	double x;
	double y;
}f[101];
double dis(int x,int y)
{
	return sqrt((f[x].x-f[y].x)*(f[x].x-f[y].x)+(f[x].y-f[y].y)*(f[x].y-f[y].y));
}
int main()
{
	int n,m;
	int i,j;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		//if(n==0)
		//	break;
		N=n;
		for(i=1;i<=N;i++)//赋最大值
			for(j=1;j<=N;j++)
				map[i][j]=MAX;
		for(i=1;i<=n;i++)
		{
			scanf("%lf %lf",&f[i].x,&f[i].y);
		}
		for(i=0;i<m;i++)
		{
			int a,b;
			double c;
			scanf("%d %d",&a,&b);
			c=dis(a,b);
			if(map[a][b]>c)
				map[a][b]=c;	
		}
		//上面的部分完全是建图map；
		//有重边的选择权值小的边  
		//记得赋值结点数N；
		if(!possible())
		{//做slove前 先检查是否是完全图
			puts("poor snoopy");
		}
		else
		{
			ans=0;
			slove();
			printf("%.2lf\n",ans);
		//	for(i=1;i< =N;i++)
		//		printf("%d ",pre[i]);
		//	printf("\n");
		}
	}
}

POJ 3522 – Slim Span(基础)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3522

题意：求一颗生成树，让最大边最小边差值最小

解法：这应该就是限制上下界的最小生成树吧，算法步骤是先给每条边排序一下，然后从每条边开始做一次kruskal，从该边后面的边开始取，看到什么时候能够
组成最小生成树，然后更新最小值，因为有各种剪枝所以这种挺暴力的方法也完全可以过，不知道有没有更好一点的方法

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
 
#define INF 0x3fffffff
struct EDGE
{
	int u;
	int v;
	int dis;
}E[20000];
int n,m;
 
int cmp(EDGE a,EDGE b)
{
	return a.dis < b.dis;
}
void init()
{
	int i,j,k;
	for(i=0;i<m;i++)
		scanf("%d %d %d",&E[i].u,&E[i].v,&E[i].dis);
	sort(E,E+m,cmp);
}
int hash[110];
int F(int a)
{
	int b = a;
	while(hash[a] != -1)
		a = hash[a];
	while(hash[b] !=-1)
	{
		hash[b] = a;
		b = hash[b];
	}
	return a;
}
void  M(int a,int b)
{
	hash[a] = b;
	return ;
}
int ans;
int work(int s)
{
	int i,j,k;
	memset(hash,-1,sizeof(hash));
	int sum = 0;
	for(i=s;i<m;i++)
	{
		if(E[i].dis - E[s].dis >= ans)
			return INF;
		int a =F(E[i].u);
		int b = F(E[i].v);
		if(a!=b)
		{
			sum ++ ;
			M(a,b);
			if(sum == n-1)
				return E[i].dis;
		}
	}
	return INF;
 
}
int main()
{
	int i;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		if(n == 0 && m == 0)
			break;
		if(m == 0)
		{
			printf("-1\n");
			continue;
		}
		init();
		ans = INF;
		ans = work(0);
		if(ans != INF)
			ans = ans - E[0].dis;
		for(i=1;i<m ;i++)
		{
			if(E[i].dis == E[i-1].dis)
				continue;
			int temp = work(i);
			if(temp == INF)
				continue;
			temp = temp -E[i].dis;
			ans = min(ans, temp);
		}
		if(ans == INF)
			ans = -1;
		printf("%d\n",ans);
	}
	return 0;
}

连通性，度数，拓扑问题：

POJ 1236 – Network of Schools(基础)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1236

题意：问添加多少边可成为双连通图

解法： 先用Trajan进行缩点，然后计算新图中各个点的入度，出度，选择入度为0的点的总和 和 出度为0 的点的总和的最大值就是答案

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "strstream"
using namespace std;
 
typedef long long LL;
typedef vector<int> VI;
typedef pair</int><int ,int> PII;
#define MP				make_pair
#define CCQ(que)			while(!que.empty()) que.pop();
#define CC(m,what)			memset(m,what,sizeof(m))
#define FS(i,a)				for( int i = 0 ; a[i] ; i ++ )
#define FF(i,a)				for( int i = 0 ; i < a ; i ++ )
#define FOR(i,a,b)			for( int i = a ; i < b ; i ++ )
#define LL(a)				a<&lt;1		//LL和RR主要用于线段树
#define RR(a)				a<&lt;1|1		//PP用于调试输出二维矩阵
#define PP(n,m,a)			puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
const double Pi = acos(-1.0);
void read(char *a)		{	freopen(a,"r",stdin);	}
void write(char *a)		{	freopen(a,"w",stdout);	}
template<class T> inline void checkmin(T &a,T b)	{if(a < 0 || a > b)a = b;}
template<class T> inline void checkmax(T &a,T b)	{if(a < b)	a = b;}
 
int dx[] = {-1,0,1,0,1,1,-1,-1};//up Right down Left
int dy[] = {0,1,0,-1,1,-1,1,-1};
//-----------------------------------------------------------------
#define M 111
struct Node{
	int v,next;
}E[200001];
int now[M],init[M];
int pre[M],Index;
int low[M],idx[M],hash[M];
int ss[M],top;
int n , nn , len;
 
void dfs(int u) 
{
	pre[u] = low[u] = Index ++;
	ss[++top] = u;
	for(int i = init[u] ; i != -1 ; i = E[i].next) 
	{
		int v = E[i].v;
		if(pre[v] == -1) 
		{
			dfs(v);
			checkmin(low[u],low[v]);
		} else if(idx[v] == -1) {
			checkmin(low[u],pre[v]);
		}
	}
	if(pre[u] == low[u]) 
	{
		int v = -1;
		while(u != v)
		{
			v = ss[top--];
			idx[v] = nn;
		}
		now[nn++] = -1;
	}
}
 
void Trajan() 
{
	memset(pre,-1,sizeof(int)*(n+1));
	memset(idx,-1,sizeof(int)*(n+1));
	Index = top = nn = 0;
	FF(i,n) 
		if(pre[i] == -1) 
		{
			dfs(i);
		}
		int ru[110]={0},chu[110]={0};
		FF(u,n)
		{
			for(int i=init[u];i!=-1;i=E[i].next)
			{
				int v=E[i].v;
				if(idx[u]!=idx[v])
				{
					ru[idx[v]]++;
					chu[idx[u]]++;
				}
			}
		}
		int a=0,b=0;
		FF(i,nn)
		{
			if(ru[i]==0)
				b++;
			if(chu[i]==0)
				a++;
		}
		if(nn==1)
			a=0;
		else
			a=max(a,b);
		printf("%d\n%d\n",b,a);
}
 
int main()
{
	int m;
	int a,b;
	int i,j,k;
 
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		memset(init,-1,sizeof(init));
		len=0;
		for(i=0;i<n;i++)
		{
			while(scanf("%d",&a))
			{
				if(a==0)
					break;
				a--;
				E[len].next=init[i];
				init[i]=len;
				E[len].v=a;
				len++;
			}
		}
		Trajan();
	}
	return 0;
}

POJ 1659 – Frogs’ Neighborhood(基础)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1659

题意：根据度序列构造图

解法： 贪心，详细证明google havel定理，每次取度数最大的点进行分配

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include<iostream>
using namespace std;
struct ff
{
	int dushu;
	int number;
}f[20];
int map[20][20];
int cmp(const void *a ,const void *b)
{
	return (*(ff *)a).dushu < (*(ff *)b).dushu ? 1 : -1;
 
}
int main()
{
	int t;
	int i,j,n;
	int tt=0;
	scanf("%d",&t);
	while(t--)
	{
		tt++;
		if(tt>1)
			printf("\n");
		scanf("%d",&n);
		for(i=0;i<n ;i++)
		{
			scanf("%d",&f[i].dushu);
			f[i].number=i;
		}
		qsort(f,n,sizeof(f[0]),cmp);
		//for(i=0;i<n;i++)
		//{
		//	printf("  %d %d\n",f[i].dushu,f[i].number);
		//}
		memset(map,0,sizeof(map));
		int flag=0;
		for(i=0;i<n;i++)
		{
			qsort(f,n,sizeof(f[0]),cmp);
			//printf("%d %d\n",i,f[i].dushu);
			if(f[n-1].dushu&lt;0)
			{
				flag=1;
				break;
			}
			int m=f[0].dushu;
			for(j=1;j<=m;j++)
			{
 
					f[0].dushu--;
					f[j].dushu--;
					map[f[j].number][f[0].number]=1;
					map[f[0].number][f[j].number]=1;
			}
		//	printf("         %d %d\n",i,f[i].dushu);
 
 
		}
		if(flag==1)
		{
			printf("NO\n");
		}
		else
		{
			printf("YES\n");
			for(i=0;i<n;i++)
			{
				for(j=0;j<n-1;j++)
					printf("%d ",map[i][j]);
				printf("%d\n",map[i][j]);
			}
		}
	}
	return 0;
}

POJ 2186 – Popular Cows(基础)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2186

题意：强连通分量缩点图出度为0的点

解法： 强连通缩点之后计算度就ok了

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

#include<iostream>
using namespace std;
#define M 10001 //保存一万条边
struct node
{
	int data;
	node *next;
};
node *f1[M];//保存正向记录的边
node *f2[M];//保存反向记录的边
int n,m;//n表示有n个点，m表示有m条边
int ans;//保存最后所给的图中包含多少个分量
int part[M];//part[1]表示所给图的点1属于第part[1]块，part[i]< =ans;
int rec[M];//保存结点的前驱。。似乎是这样。。（不懂）
bool p[M];
int a[50001],b[50001];//a[i],b[i]表示a[i],b[i]之间有一条边；
void clear(node *p)
{
	if(p!=NULL)
	{
		clear(p->next);
		p->next=NULL;
	}
 
	return ;
}
void Input()
{
	int i;
	memset(part,0,sizeof(part));
	memset(rec,0,sizeof(rec));
	memset(p,0,sizeof(p));
	ans=0;//初始化~
	for(int i=0;i<n ;i++)
	{
		if(f1[i]!=NULL)
		{
			clear(f1[i]);
			f1[i]->next=NULL;
		}
		if(f2[i]!=NULL)
		{
			clear(f2[i]);
			f2[i]->next=NULL;
		}
	}//清理链表
	node *temp;
	for(i=1;i< =m;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		temp = new node;        //正向记录边    f1
		temp -> data = b[i];
		temp -> next =f1[a[i]];
		f1[a[i]] = temp;
		temp = new node ;       //反向记录边 f2
		temp -> data = a[i];
		temp -> next = f2[b[i]];
		f2[b[i]] = temp;		
	}
}
void      DFS_1(int x)               //第一次DFS ,边不反向
{
	if (p[x]) return ;
	p[x] = true;
	node * temp;
	temp = f1[x];
	while (temp != NULL)
	{
		DFS_1(temp -> data);
		temp = temp -> next;     
	}         
	rec[0]++; rec[rec[0]] = x; //回溯记录点
}
void      DFS_2(int x)             //第2次DFS ，边反向
{
	if (p[x]) return ;
	p[x] = true;
	node * temp;
	temp = f2[x];
	while (temp != NULL)
	{
		DFS_2(temp -> data);
		temp = temp -> next;     
	}        
	part[x] = ans;           //x点属于ans块
}
void      Slove()
{
	for (int i = 1 ; i < = n ; i++)
		DFS_1(i);         
	memset(p , 0 , sizeof p);
	for (int i = n ; i >= 1 ; i-- ) //把回溯记录的点反向 DFS_2
		if (!p[rec[i]])                  //如果这个点没有访问过就那就增加一块
		{
			ans++;
			DFS_2(rec[i]);              
		}
}
void Output()
{
	//printf("%d\n",ans);
	int i;
	if(ans==1)
	{
		printf("%d\n",n);   
		return ;
	}
 
	int aa[10001]={0};
	for(i=1;i< =n;i++)
	{
		aa[part[i]]++;
	}
	int duru[10001]={0};
	int duchu[10001]={0};
	//for(i=1;i<=N;i++)
	//	printf("%d ",part[i]);
	for(i=1;i<=m;i++)
	{
 
		if(part[a[i]]!=part[b[i]])
		{
			duchu[part[a[i]]]++;
			//	duru[part[b[i]]]++;
		}
	}
	int da=0;
	int id;
	for(i=1;i<=ans;i++)
	{
		if(duchu[i]==0)
		{
			da++;
			id=i;
		}
	}
	if(da > 1)
	{
		printf("0\n");
	}
	else
	{
		printf("%d\n",aa[id]);
	}
}
int main()
{
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		Input();
		Slove();
		Output();
	}
	return 0;
}</n></iostream>

POJ 2762 – Going from u to v or from v to u?(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2762

题意：单向连通图判定

解法： 判断是否对月任意两个点有s->t或者t->s，先缩点然后看缩点后的图中是否能够组成一条长链，用dfs,bfs,dp都行

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

//I believe in brother spring!!
#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "set"
#include "iostream"
#include "sstream"
#include "queue"
using namespace std;
 
typedef long long LL;
typedef vector<int> VI;
typedef pair</int><int ,int> PII;
#define MP				make_pair
#define CCQ(que)			while(!que.empty()) que.pop();
#define CC(m,what)			memset(m,what,sizeof(m))
#define FS(i,a)				for( int i = 0 ; a[i] ; i ++ )
#define FF(i,a)				for( int i = 0 ; i < a ; i ++ )
#define FOR(i,a,b)			for( int i = a ; i < b ; i ++ )
#define PP(n,m,a)			puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
const double Pi = acos(-1.0);
void read(char *a)		{	freopen(a,"r",stdin);	}
void write(char *a)		{	freopen(a,"w",stdout);	}
template<class T> inline void checkmin(T &a,T b)	{if(a < 0 || a > b)a = b;}
template<class T> inline void checkmax(T &a,T b)	{if(a < b)	a = b;}
 
int dx[] = {-1,0,1,0,1,1,-1,-1};//up Right down Left
int dy[] = {0,1,0,-1,1,-1,1,-1};
//-----------------------------------------------------------------
 
#define M 1101
struct NODE
{
	int v;
	int next;
}E[6101];
int now[M],init[M];
int pre[M],index;
int low[M],idx[M],hash[M];
int ss[M],top;
int n,nn,len;
int m;
void dfs(int u)
{
	pre[u]=low[u]=index++;
	ss[++top]=u;
	for(int i=init[u];i!=-1;i=E[i].next)
	{
		int v=E[i].v;
		if(pre[v]==-1)
		{
			dfs(v);
			checkmin(low[u],low[v]);
		}
		else if(idx[v]==-1)
		{
			checkmin(low[u],pre[v]);
		}
	}
	if(pre[u]==low[u])
	{
		int v=-1;
		while(u!=v)
		{
			v=ss[top--];
			idx[v]=nn;
		}
		now[nn++]=-1;
	}
}
 
void trajan()
{
	memset(pre,-1,sizeof(pre));
	memset(idx,-1,sizeof(idx));
	index=top=nn=0;
	int i;
	for(i=0;i<n;i++)
	{
		if(pre[i]==-1)
			dfs(i);
	}
	memset(hash,-1,sizeof(hash));
	for(int u=0;u<n;u++)
	{
		for(i=init[u];i!=-1 ;i=E[i].next)
		{
			int v=E[i].v;
			if(idx[u]!=idx[v] && hash[idx[u]]!=idx[v])
			{
				hash[idx[u]]=idx[v];
				E[len].next=now[idx[u]];
				E[len].v=idx[v];
				now[idx[u]]=len++;
			}
		}
	}
}
 
void addedge(int u,int v)
{
	E[len].v=v;
	E[len].next=init[u];
	init[u]=len++;
}
int a[6100],b[6100];
void IN()
{
	int i,j,k;
 
	len=0;
	memset(init,-1,sizeof(init));
	for(i=0;i<m;i++)
	{
		scanf("%d %d",&a[i],&b[i]);
		a[i]--;b[i]--;
		addedge(a[i],b[i]);
	}
 
}
int main()
{
	int i,j,k;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&m);
		IN();
		trajan();
 
		//printf("  %d\n",nn);
		//for(i=0;i<n;i++)
		//	printf("%d ",idx[i]);
 
		int flag=0;
		int du[M]={0};
		for(i=0;i<nn;i++)
		{
			for(j=now[i];j!=-1;j=E[j].next)
			{
				du[E[j].v]++;
			}
		}
		int s=-1;
		for(i=0;i<nn;i++)
		{
			if(du[i]==0)
			{
				if(s!=-1)
					break;
				s=i;
			}
		}
		int ans=1;
		if(i<nn)
			puts("No");
		else
		{
			int flag=0;
			while(1)
			{
				int temp=-1;
 
				for(i=now[s];i!=-1;i=E[i].next)
				{
					du[E[i].v]--;
					if(du[E[i].v]==0)
					{
						if(temp!=-1)
						{
							flag=1;
							break;
						}
						temp=E[i].v;
					}
				}
				if(flag==1)
					break;
				if(temp==-1)
					break;
				s=temp;
				ans++;
			}
		//	printf("  %d %d\n",ans,nn);
			if(!flag&&ans==nn)
				puts("Yes");
			else
				puts("No");
		}
	}
	return 0;
}

POJ 2914 – Minimum Cut

http://acm.pku.edu.cn/JudgeOnline/problem?id=2914

题意：无向图全局最小割

解法： Stoer-Wagner算法，模板题，可能不知道的会用最大流尝试

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
using namespace std;
int mat[600][600];
int res;
 
void Mincut(int n) {
    int node[600], dist[600];
    bool visit[600];
    int i, prev, maxj, j, k;
    for (i = 0; i < n; i++)
        node[i] = i;
    while (n > 1) {
        int maxj = 1;
        for (i = 1; i < n; i++) { //初始化到已圈集合的割大小
            dist[node[i]] = mat[node[0]][node[i]];
            if (dist[node[i]] > dist[node[maxj]])
                maxj = i;
        }
        prev = 0;
        memset(visit, false, sizeof (visit));
        visit[node[0]] = true;
        for (i = 1; i < n; i++) {
            if (i == n - 1) { //只剩最后一个没加入集合的点，更新最小割
                res = min(res, dist[node[maxj]]);
                for (k = 0; k < n; k++) //合并最后一个点以及推出它的集合中的点
                    mat[node[k]][node[prev]] = (mat[node[prev]][node[k]] += mat[node[k]][node[maxj]]);
                node[maxj] = node[--n]; //缩点后的图
            }
            visit[node[maxj]] = true;
            prev = maxj;
            maxj = -1;
            for (j = 1; j < n; j++)
                if (!visit[node[j]]) { //将上次求的maxj加入集合，合并与它相邻的边到割集
                    dist[node[j]] += mat[node[prev]][node[j]];
                    if (maxj == -1 || dist[node[maxj]] < dist[node[j]])
                        maxj = j;
                }
        }
 
    }
    return;
}
 
int main() {
    int n, m, a, b, v;
    while (scanf("%d%d", &n, &m) != EOF) {
        res = (1 << 29);
        memset(mat, 0, sizeof (mat));
        while (m--) {
            scanf("%d%d%d", &a, &b, &v);
            mat[a][b] += v;
            mat[b][a] += v;
        }
        Mincut(n);
        printf("%d\n", res);
    }
}

POJ 2942 – Knights of the Round Table(难)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2942

题意：求双联通分量(或称块)中是否含奇圈

解法： 求出双连通分量后做黑白染色进行二分图图判定，这是为数不多的能够练习点的双连通分量的题目，还有一题是 http://acm.hdu.edu.cn/showproblem.php?pid=3394 momodi出的，但是这题题意没写清楚要求的是点的双连通分量。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250

#include<iostream>
using namespace std;
#include<queue>
#include<stdio .h>
#include<string .h>
 
#include<vector>
 
 
//邻接表形式
#define M 2110
struct EDGE
{
	int v;
	int flag;//1代表是桥边
	int next;
}E[21000000 ];
 
int st[M*10];
int len;
 
int num;//边的条数 初始化为0
int head[M];//初始化为-1
int C[M];/*0 白色:没遍历过  1 灰色:遍历过未检查 2 黑色:检查过*/
int ancestor[M];/*记录和k及k的子孙相连的辈分最高的祖先所在的深度*/
int D[M];/*记录节点的深度*/
int root;//保存根节点
bool cut[M];//记录割点信息
int A[M];//记录时间戳，用来保存被遍历的时间
int time;//时间戳
 
/*(1):用来求割点，(2):用来求桥边*/
int ans[M];
int temp[M*10];
int ok;
int pan;
int hash[M];
int du[M];
int qq;
int col[M];
void slove()
{
	//dian baocun zai temp li ;
	//ruguo shi jiquan jiu hash ans
 
	int flag = 0;
	queue<int>Q;
	if(ok&lt;3)
		return ;
	Q.push(temp[0]);
	int i;
	col[temp[0]] = pan;
	while(!Q.empty())
	{
		int u =Q.front();
		Q.pop();
		for(i=head[u];i!=-1;i=E[i].next)
		{
			int v = E[i].v;
 
			if(hash[v] != pan)
				continue;
			if(col[u] == col[v])
			{
				flag = 1;
				break;
			}
			if(col[v] ==pan || col[v] == (pan^1))
				continue;
			Q.push(v);
			col[v] = col[u]^1;
		}
	}
	if(flag == 1)
	{
		for(i=0;i<ok ;i++)
		{
			ans[temp[i]] = 1;
		}
	}
	pan+=2;
}
 
void dfs(int k,int father,int deep)
{
	/*节点编号k，k的父亲节点, 深度*/
	int i;
	int tot;/*顶点k的儿子个数*/
	int v;
	C[k]=1;
	D[k]=deep;
	ancestor[k]=deep,tot=0;//(1)
 
	//printf("%d\n",k);
	//for(i=1;i<=N;i++)
	for(i=head[k];i!=-1;i=E[i].next)
	{
 
		v=E[i].v;
		//printf("   %d -> %d\n",k,v);
 
		if( v!=father && C[v]==1 )
		{
		//	len ++;//
		//	st[len] = v;//
 
			ancestor[k]=min(ancestor[k],D[v]);       //(1)
 
		}
		if( C[v]==0 )
		{
			len ++;//
			st[len] = v;//
 
			dfs(v,k,deep+1);
 
			tot=tot+1;  //(1)
			ancestor[k]=min(ancestor[k],ancestor[v]);   //(1)
			if( ( k==root && tot>1 ) || (k!=root && ancestor[v] >= D[k]) )  //(1)
			{
				ok = 0;
				while(1)
				{
				//	printf("%d ",st[len]);
					temp[ok++] = st[len];
					int tt = st[len--];
					if(hash[tt] != pan)
					{
						hash[tt] = pan;
 
					}
					if(st[len+1] == v)
					{
						break;
					}
 
				}
				temp[ok++] = k;
					int tt = k;
					if(hash[tt] != pan)
					{
						hash[tt] = pan;
 
					}
				slove();
			//	printf("\n");
				cut[k]=true;   //(1)
			//	printf("cut  %d\n",k);
			}
 
			//if(ancestor[v] > D[k])   //(2)
			//{
			//	E[i].flag=1;
			//	E[i^1].flag=1;
			//}
		}
	}
	C[k]=2;
	time++;
	A[k]=time;
}
 
void addedge(int u,int v)
{//无向边
	E[num].flag=0;
	E[num].v=v;
	E[num].next=head[u];
	head[u]=num++;
 
	//E[num].flag=0;
	//E[num].v=u;
	//E[num].next=head[v];
	//head[v]=num++;
}
 
 
int map[1100][1100];
int main()
{
	int n,m;
	int i,j,k;
	int a,b;
 
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		memset(du,0,sizeof(du));
		if(n+m == 0)
			break;
		pan = 0;
		memset(hash,-1,sizeof(hash));
		memset(col,-1,sizeof(col));
		memset(map,0,sizeof(map));
		for(i=0;i<m ;i++)
		{
			scanf("%d %d",&a,&b);
		//	du[a] ++ ;
		//	du[b] ++ ;
			map[a][b] = map[b][a] = 1;
		}
		memset(head,-1,sizeof(head));
		memset(C,0,sizeof(C));
        memset(cut,false,sizeof(cut));
        memset(A,0,sizeof(A));
 
		num = 0;
		for(i=1;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				if(map[i][j] == 0)
				{
					addedge(i,j);
					addedge(j,i);
					du[i]++;
					du[j]++;
				}
			}
		}
 
		memset(ans,0,sizeof(ans));
		for(i=1;i<=n;i++)
			if(C[i] == 0)
			{
				root = i;
				len = 0;
				st[len] = i;
				dfs(i,0,1);
				ok = 0;qq = 0;
				while(len != -1)
				{
					temp[ok++] = st[len];
					int tt = st[len--];
					if(hash[tt] != pan)
					{
						hash[tt] = pan;
						qq++;
					}
				//	printf("%d ",st[len+1]);
				}
			//	printf("\n");
				slove();
			}
		int cnt = 0;
		for(i=1;i<=n;i++)
			if(ans[i])
				cnt++;
		printf("%d\n",n-cnt);
	}
	return 0;
}

POJ 3177 – Redundant Paths(中等)
POJ 3352 – Road Construction(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3177
http://acm.pku.edu.cn/JudgeOnline/problem?id=3352

题意：添加多少条边可成为双向连通图

解法： 先缩点，然后看度为1的点的个数比如为x,那么答案就是(x+1)/2。还有一个是有向图添加多少边变成强连通，具体可看POJ-1236

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

#include<iostream>
using namespace std;
#include<string .h>
#include<queue>
/*
求无向图的割点 和 无向图的桥边
*/
#define MNUM 1020 //设置大小
int d[MNUM];//树的深度
int map[MNUM][MNUM];//保存邻接矩阵
int n;//有n条边的邻接矩阵
int color[MNUM];//染色
int t[MNUM];//记录每个点的时间戳
int tt;//时间戳
int ans[MNUM];//记录和k及k的子孙相连的辈份最高的祖先所处的深度
int root;//设置树的根节点 
int bridge[MNUM][MNUM]; //保存桥边
int cut[101];//保存割点
int MIN(int x,int y)
{
	if(x>y)
		return y;
	return x;
}
void dfs(int k,int fa,int deep)
{//结点编号k；k的父亲结点;深度;
	int i,tot;
	color[k]=1;
	d[k]=deep;
	ans[k]=deep;
	tot=0;
 
	for(i=1;i< =n;i++)
	{
		if(map[i][k]==1 && i!=fa && color[i]==1)
			ans[k]=MIN(ans[k],d[i]);
		if(map[i][k]&&color[i]==0)
		{
			dfs(i,k,deep+1);
 
			tot=tot+1;
			ans[k]=MIN(ans[k],ans[i]);
			if((k==root && tot>1) || (k!=root && ans[i]>=d[k]))
				cut[k]=1;
			if(ans[i]>d[k]) //2  2 是用来求桥边的  
			{
				bridge[k][i]=1;//2
				bridge[i][k]=1;
			//	printf("dasd\n");
 
			}
		}
	}
	color[k]=2;
	tt++;
	t[k]=tt;
}
int a[10001];
int b[10001];
int w[MNUM][MNUM];
int x[1001];
int y[1001];
int shu=0;
int main()
{
	int i,j;
	int m;
	scanf("%d %d",&n,&m);
	{
		for(i=0;i<m ;i++)
		{
			scanf("%d %d",&a[i],&b[i]);
			if(map[a[i]][b[i]]==1)
			{
				x[shu]=a[i];
				y[shu]=b[i];
				shu++;
				continue;
			}
			map[a[i]][b[i]]=1;
			map[b[i]][a[i]]=1;
 
		}
	}
	root=1;
	dfs(1,-1,0);
 
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
			if(bridge[i][j]==1 && map[i][j]==1)
			{
			//	printf("sad\n");
				map[i][j]=map[j][i]=0;
			}
		}
 
	int nu=1;
	int hash[1001]={0};
	for(i=1;i<=n;i++)
	{
		if(hash[i]==0)
		{
			hash[i]=nu;
			queue<int>Q;
			Q.push(i);
			while(!Q.empty())
			{
				int now=Q.front();
				Q.pop();
				for(j=1;j< =n;j++)
				{
					if(map[now][j]==1&& hash[j]==0)
					{
						hash[j]=nu;
						Q.push(j);
					}
				}
			}
			nu++;
		}
 
	}
	for(i=0;i<shu;i++)
	{
		if(hash[x[i]]!=hash[y[i]])
		{
			int tt=hash[x[i]];
			for(j=1;j<=n;j++)
			{
				if(hash[j]==hash[y[i]])
					hash[j]=tt;
			}
		}
	}
	int du[1001]={0};
	for(i=0;i<m;i++)
	{
		if(hash[a[i]]!=hash[b[i]])
		{
			du[hash[a[i]]]++;
			du[hash[b[i]]]++;
		}
	}
 
	int z=0;
	for(i=1;i<nu;i++)
		if(du[i]==1)
			z++;
	printf("%d\n",(z+1)/2);
	return 0;
}

POJ 3249 – Test for Job(基础)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3249

题意：多源多汇的最短路

解法： 直接用spfa求最短路会超时，用DIJ应该没问题，所以改用广搜，类似于拓扑的搜法顺利解决

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include<iostream>
using namespace std;
#include<queue>
#include<stdio .h>
#include<string .h>
#include<vector>
 
#define INF 0x3fffffff
struct EDGE
{
	int v;
	int next;
	int dis;
}E[1100000];
 
int num;
int head[110000];
 
void addedge(int u,int v,int c)
{
	//printf("  %d %d %d\n",u,v,c);
	E[num].v = v;
	E[num].dis =c;
	E[num].next = head[u];
	head[u] = num++;
}
 
void init()
{
	memset(head,-1,sizeof(head));
	num = 0;
}
int dis[110000];
int hash[110000];
int val[110000];
int du[110000];
int in[110000];
 
void spfa(int s,int t)
{
	int i,j,k;
	for(i=0;i< =t;i++)
		dis[i] = INF;
	queue<int>Q;
	Q.push(s);
	dis[s] = 0;
	while(!Q.empty())
	{
		int u =Q.front();
		Q.pop();
		for(i=head[u];i!=-1;i=E[i].next)
		{
			int v = E[i].v;
			if(dis[v] > dis[u]+E[i].dis)
				dis[v] = dis[u] + E[i].dis;
			du[v] -- ;
			if(du[v] == 0)
				Q.push(v);
		}
	}
}
 
int main()
{
	int n,m;
	int i,j,k;
	int a,b;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		init();
		memset(du,0,sizeof(du));
		memset(in,0,sizeof(in));
		for(i=1;i< =n;i++)
			scanf("%d",&val[i]);
		for(i=0;i<m;i++)
		{
			scanf("%d %d",&a,&b);
			du[b] ++ ;
			in[a] ++ ;
			addedge(a,b,-val[b]);
		}	
		int s = 0;
		int t = n+1;
		for(i=1;i<=n;i++)
		{
			if(du[i] == 0)
			{
				addedge(s,i,-val[i]);
				du[i]++;
			}
			if(in[i] == 0)
			{
				addedge(i,t,0);
				du[t]++;
			}
		}
		spfa(s,t);
		printf("%d\n",-dis[t]);
	}
	return 0;
}

POJ 3694 – Network(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3694

题意：双连通分量+并查集

解法： 先缩点找桥，然后建立新图，建立一棵树，对于每次添加的边，找到各个点到达他们的LCA的路径上有多少边是桥，然后统计即可，对于求LCA，不必特殊的解法，只需记录各个点的deep和pre，然后根据pre寻找即可，不会超时~

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

#include<iostream>
using namespace std;
#include<queue>
#include<stdio .h>
#include<string .h>
#include<vector>
#define M 200100
struct EDGE
{
	int v;
	int flag;//1代表是桥边
	int next;
}E[2000111];
 
int num;//边的条数 初始化为0
int head[M];
int now[M];
int C[M];
int ancestor[M];
int D[M];
int root;
bool cut[M];
int A[M];
int time;
void dfs(int k,int father,int deep)
{
	int i;
	int tot;
	int v;
 
	C[k]=1;
	D[k]=deep;
	ancestor[k]=deep,tot=0;//(1)
	for(i=head[k];i!=-1;i=E[i].next)
	{
		v=E[i].v;
		if(v==father)
		{
			father = -1;
			continue;
		}
		if( v!=father && C[v]==1 )
			ancestor[k]=min(ancestor[k],D[v]);       //(1)
		if( C[v]==0 )
		{
			dfs(v,k,deep+1);
 
			tot=tot+1;  //(1)
			ancestor[k]=min(ancestor[k],ancestor[v]);   //(1)
			if( ( k==root && tot>1 ) || (k!=root && ancestor[v] >= D[k]) )  //(1)
			{
				cut[k]=true;   //(1)
			}
 
			if(ancestor[v] > D[k])   //(2)
			{
				E[i].flag=1;
				E[i^1].flag=1;
			}
		}
	}
	C[k]=2;
	time++;
	A[k]=time;
}
 
void addedge(int u,int v)
{//无向边
	E[num].flag=0;
	E[num].v=v;
	E[num].next=head[u];
	head[u]=num++;
 
	E[num].flag=0;
	E[num].v=u;
	E[num].next=head[v];
	head[v]=num++;
}
void addedge2(int u,int v)
{//无向边
	E[num].flag=0;
	E[num].v=v;
	E[num].next=now[u];
	now[u]=num++;
}
int idx[M];
void init()
{
	memset(head,-1,sizeof(head));
	memset(ancestor,0,sizeof(ancestor));
	num = 0;
	memset(C,0,sizeof(C));
	memset(D,0,sizeof(D));
	memset(cut,0,sizeof(cut));
	memset(now,-1,sizeof(now));
	memset(idx,0,sizeof(idx));
	time = 0;
}
 
void bfs(int s,int z)
{
	queue<int>Q;
	idx[s] = z;
	Q.push(s);
	while(!Q.empty())
	{
		int u = Q.front();
		Q.pop();
		for(int i = head[u];i!=-1;i=E[i].next)
		{
			if(E[i].flag )
				continue;
			int v = E[i].v;
			if(idx[v] == 0)
			{
				idx[v] = z;
				Q.push(v);
			}
		}
	}
}
int pre[M];
int deep[M];
int hash[M];
void tree(int s,int dd,int pp,int id)
{
	int i,j,k;
	deep[s] = dd;
	hash[s] = 1;
	for(i=now[s];i!=-1;i=E[i].next)
	{
		int v = E[i].v;
		if(v == pp)
		{
			E[i].flag = 1;
			continue;
		}
		pre[v] = s;
		tree(v,dd+1,s,i);
	}
}
int work(int a,int b)
{
	int ans = 0;
	while(deep[a] > deep[b])
	{
		ans += hash[a];
		hash[a] = 0;
		a = pre[a];
	}
	while(deep[b] > deep[a])
	{
		ans += hash[b];
		hash[b] = 0;
		b = pre[b];
	}
	while(a != b)
	{
		ans += hash[a];
		hash[a] = 0;
		a = pre[a];
		ans += hash[b];
		hash[b] = 0;
		b = pre[b];
	}
	return ans;
}
int main()
{
	int n,m;
	int p;
	int a,b,c;
	int i,j,k;
	int ca = 0;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		ca++;
		if(n == 0 && m == 0)
			break;
		init();
		for(i=0;i<m ;i++)
		{
			scanf("%d %d",&a,&b);
			addedge(a,b);
		}
		root = 1;
		dfs(1,-1,1);
 
		int z = 1;
		for(i=1;i<=n;i++)
		{
			if(idx[i] == 0)
			{
				bfs(i,z);
				z++;
			}
		}//fenlei
		for(i=1;i<=n;i++)
		{
			for(j=head[i];j!=-1;j=E[j].next)
			{
 
				if(E[j].flag)
				{
					addedge2(idx[i],idx[E[j].v]);
				}
			}
		}
		tree(1,1,-1,-1);
		int sum = z-2;
		printf("Case %d:\n",ca);
		scanf("%d",&p);
		while(p--)
		{
			scanf("%d %d",&a,&b);
			sum -=work(idx[a],idx[b]);
			printf("%d\n",sum);
		}
		printf("\n");
	}
	return 0;
}

本文引用地址： 

上一篇： 下一篇：

发表评论有 5 位网友发表了评论  

  1. Tanky Woo 说：
    2010/09/06 - 10:31 上午

    听小amb说你是图神，特地再来Orz一番。

    :razz:
    顺便把你的方法看看，我图是最薄弱的。。。

    [回复]

    回复
  2. lct_3 说：
    2010/09/04 - 10:48 下午

    全局最小割确实可以 枚举+最大流 解决,不过POJ 2914用最大流会TLE..

    [回复]

    Starvae 回复:
    9月 4th, 2010 at 11:08 下午

    恩，记得去年集训的时候某天上午做了一个类似求最小割的，可以用枚举+最大流解决，结果下午多校联合的时候刚好碰到了全局最小割，然后很自信的枚举+最大流，结果呵呵~ 最后还被yifenfei鄙视了。。

    [回复]

    回复
  3. crbtmac 说：
    2010/09/04 - 9:55 上午

    POJ 1679 – The Unique MST 你的解法貌似是错的。。。
    给你组数据
    1
    4 4
    1 2 1
    2 3 5
    3 4 3
    1 4 5

    [回复]

    Starvae 回复:
    9月 5th, 2010 at 12:47 上午

    恩~ 感谢提醒~

    [回复]

    回复

添加新的评论浏览评论»  

表情
icon_wink.gif icon_neutral.gif icon_mad.gif icon_twisted.gif icon_smile.gif icon_eek.gif icon_sad.gif icon_rolleyes.gif icon_razz.gif icon_redface.gif icon_surprised.gif icon_mrgreen.gif icon_lol.gif icon_idea.gif icon_biggrin.gif icon_evil.gif icon_cry.gif icon_cool.gif icon_arrow.gif icon_confused.gif icon_question.gif icon_exclaim.gif 



注意：
1、本站启用了审核机制，你的留言可能稍后才会显示，请不要重复提交，谢谢。
2、留言时的头像是Gravatar提供的服务。想设置的看这里。
3、评论者允许使用'@user空格'的方式将自己的评论通知另外评论者。

    • ©WordPress. Modfied by Starvae | 杭州电子科技大学 返回顶部