poj3352

maksyuki 发表于 oj 分类，标签: 图论-求解割点\割边(Tarjan), 数据结构-并查集

22 1月 2016

Road Construction

It's almost summer time, and that means that it's almost summer construction time! This year, the good people who are in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the various roads that lead between the various tourist attractions on the island.

The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.

Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to travel between two tourist attractions, even if the construction company works on only one road at any particular time.

So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem. It has been decided that new roads will have to be built between the various attractions in such a way that in the final configuration, if any one road is undergoing construction, it would still be possible to travel between any two tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.

Input

The first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by a space, indicating that a road exists between the attractions labelled v and w. Note that you may travel in either direction down each road, and any pair of tourist attractions will have at most one road directly between them. Also, you are assured that in the current configuration, it is possible to travel between any two tourist attractions.

Output

One line, consisting of an integer, which gives the minimum number of roads that we need to add.

Sample Input

Sample Input 1

10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10

Sample Input 2

3 3

1 2

2 3

1 3

Sample Output

Output for Sample Input 1

Output for Sample Input 2

Source

CCC 2007

题目类型：无向图求割边(Tarjan)+缩点(并查集)

算法分析：首先可知在同一个重连通分量(边)中的点之间一定存在至少两条独立的路径，即可以不用考虑在同一个重连通分量中的点之间建路。这样的话可以将同一个连通分量缩成一个点，最后得到的图一定是一个树，且树中的边一定是割边(没有缩掉)。最后在两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先路径上所有的点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1) / 2次(leaf为树中叶子节点的个数)把所有点收缩到了一起。这里使用栈来记录每次找到的重连通分量(边)，使用并查集来缩点，注意这里任意两点之间没有重边！！！

/*************************************************
Author        :supermaker
Created Time  :2016/1/22 10:58:19
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 5000 + 6;

int dfn[maxn], low[maxn], vis[maxn];
int n, m, id;
stack <PII> sta;
vector <int> g[maxn];
set <PII> seta;
int parent[maxn], deg[maxn], part[maxn];

int UnFind (int val)
{
	if (parent[val] == val) return val;
	else return parent[val] = UnFind (parent[val]);
}

void Init (int rt)
{
	for (int i = 0; i < maxn; i++)
		parent[i] = i;
	
	for (int i = 0; i < maxn; i++)
		g[i].clear ();
	seta.clear ();
	dfn[rt] = low[rt] = id = 1;
	memset (vis, 0, sizeof (vis));
	memset (deg, 0, sizeof (deg));
	vis[rt] = 1;
	while (!sta.empty ()) sta.pop ();
}

void SS ()
{
	for (int u = 1; u <= n; u++)
		if (part[u])
		{
			for (int i = 0; i < g[u].size (); i++)
			{
				int v = g[u][i];
				if (part[v])
					parent[UnFind(v)] = UnFind (u);
			}
		}
}

void dfs (int u, int par)
{
	for (int i = 0; i < g[u].size (); i++)
	{
		int v = g[u][i];
		if (seta.find (PII (u, v)) == seta.end ())
		{
			seta.insert (PII (u, v));
			seta.insert (PII (v, u));
			sta.push (PII (u, v));
			if (!vis[v])
			{
				vis[v] = 1;
				dfn[v] = low[v] = ++id;
				dfs (v, u);
				low[u] = min (low[u], low[v]);
				if (low[v] > dfn[u])
				{
					memset (part, 0, sizeof (part));
					//bool is_have = false;
					while (!sta.empty ())
					{
						PII temp = sta.top (); sta.pop ();
						if ((temp.first == u && temp.second == v) || (temp.first == v && temp.second == u))
							break;
						part[temp.first] = part[temp.second] = 1;
						//printf (" %d-%d ", temp.first, temp.second);
						//is_have = true;
					}
					//if (is_have)
					//	puts ("");
					SS ();
				}
			}
			else if (v != par)
				low[u] = min (low[u], dfn[v]);	
		}
	}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		Init (1);
		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			g[u].push_back (v);
			g[v].push_back (u);
		}
		dfs (1, -1);

		seta.clear ();
		for (int u = 1; u <= n; u++)
			for (int i = 0; i < g[u].size (); i++)
			{
				int v = g[u][i];
				if (seta.find (PII (u, v)) != seta.end ()) continue;
				seta.insert (PII (u, v)), seta.insert (PII (v, u));
				if (UnFind (u) != UnFind (v))
					deg[UnFind(u)]++, deg[UnFind(v)]++;
			}

		int res = 0;
		for (int i = 1; i <= n; i++)
		{
			//cout << "i = " << i << " deg[i] = " << deg[i] << endl;
			if (deg[i] == 1) 
				res++;
		}

		printf ("%d\n", (res + 1) / 2);
	}
    return 0;
}

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

/*************************************************

Author :supermaker

Created Time :2016/1/22 10:58:19

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5000 + 6;

int dfn[maxn], low[maxn], vis[maxn];

int n, m, id;

stack <PII> sta;

vector <int> g[maxn];

set <PII> seta;

int parent[maxn], deg[maxn], part[maxn];

int UnFind (int val)

{

if (parent[val] == val) return val;

else return parent[val] = UnFind (parent[val]);

}

void Init (int rt)

{

for (int i = 0; i < maxn; i++)

parent[i] = i;

for (int i = 0; i < maxn; i++)

g[i].clear ();

seta.clear ();

dfn[rt] = low[rt] = id = 1;

memset (vis, 0, sizeof (vis));

memset (deg, 0, sizeof (deg));

vis[rt] = 1;

while (!sta.empty ()) sta.pop ();

}

void SS ()

{

for (int u = 1; u <= n; u++)

if (part[u])

{

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i];

if (part[v])

parent[UnFind(v)] = UnFind (u);

}

void dfs (int u, int par)

{

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i];

if (seta.find (PII (u, v)) == seta.end ())

{

seta.insert (PII (u, v));

seta.insert (PII (v, u));

sta.push (PII (u, v));

if (!vis[v])

{

vis[v] = 1;

dfn[v] = low[v] = ++id;

dfs (v, u);

low[u] = min (low[u], low[v]);

if (low[v] > dfn[u])

{

memset (part, 0, sizeof (part));

//bool is_have = false;

while (!sta.empty ())

{

PII temp = sta.top (); sta.pop ();

if ((temp.first == u && temp.second == v) || (temp.first == v && temp.second == u))

break;

part[temp.first] = part[temp.second] = 1;

//printf (" %d-%d ", temp.first, temp.second);

//is_have = true;

}

//if (is_have)

// puts ("");

SS ();

}

else if (v != par)

low[u] = min (low[u], dfn[v]);

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &m) != EOF)

{

Init (1);

for (int i = 1; i <= m; i++)

{

int u, v;

scanf ("%d%d", &u, &v);

g[u].push_back (v);

g[v].push_back (u);

}

dfs (1, -1);

seta.clear ();

for (int u = 1; u <= n; u++)

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i];

if (seta.find (PII (u, v)) != seta.end ()) continue;

seta.insert (PII (u, v)), seta.insert (PII (v, u));

if (UnFind (u) != UnFind (v))

deg[UnFind(u)]++, deg[UnFind(v)]++;

}

int res = 0;

for (int i = 1; i <= n; i++)

{

//cout << "i = " << i << " deg[i] = " << deg[i] << endl;

if (deg[i] == 1)

res++;

}

printf ("%d\n", (res + 1) / 2);

}

return 0;

}

算法分析：也可以直接使用POJ3177求解无向图(有重边)的方法来求解

链接：http://www.maksyuki.com/?p=2719

poj2942

maksyuki 发表于 oj 分类，标签: 图论-求解割点\割边(Tarjan)

21 1月 2016

Knights of the Round Table

Being a knight is a very attractive career: searching for the Holy Grail, saving damsels in distress, and drinking with the other knights are fun things to do. Therefore, it is not very surprising that in recent years the kingdom of King Arthur has experienced an unprecedented increase in the number of knights. There are so many knights now, that it is very rare that every Knight of the Round Table can come at the same time to Camelot and sit around the round table; usually only a small group of the knights isthere, while the rest are busy doing heroic deeds around the country.

Knights can easily get over-excited during discussions-especially after a couple of drinks. After some unfortunate accidents, King Arthur asked the famous wizard Merlin to make sure that in the future no fights break out between the knights. After studying the problem carefully, Merlin realized that the fights can only be prevented if the knights are seated according to the following two rules:

The knights should be seated such that two knights who hate each other should not be neighbors at the table. (Merlin has a list that says who hates whom.) The knights are sitting around a roundtable, thus every knight has exactly two neighbors.
An odd number of knights should sit around the table. This ensures that if the knights cannot agree on something, then they can settle the issue by voting. (If the number of knights is even, then itcan happen that yes" and no" have the same number of votes, and the argument goes on.)

Merlin will let the knights sit down only if these two rules are satisfied, otherwise he cancels the meeting. (If only one knight shows up, then the meeting is canceled as well, as one person cannot sit around a table.) Merlin realized that this means that there can be knights who cannot be part of any seating arrangements that respect these rules, and these knights will never be able to sit at the Round Table (one such case is if a knight hates every other knight, but there are many other possible reasons). If a knight cannot sit at the Round Table, then he cannot be a member of the Knights of the Round Table and must be expelled from the order. These knights have to be transferred to a less-prestigious order, such as the Knights of the Square Table, the Knights of the Octagonal Table, or the Knights of the Banana-Shaped Table. To help Merlin, you have to write a program that will determine the number of knights that must be expelled.

Input

The input contains several blocks of test cases. Each case begins with a line containing two integers 1 ≤ n ≤ 1000 and 1 ≤ m ≤ 1000000 . The number n is the number of knights. The next m lines describe which knight hates which knight. Each of these m lines contains two integers k1 and k2 , which means that knight number k1 and knight number k2 hate each other (the numbers k1 and k2 are between 1 and n ).

The input is terminated by a block with n = m = 0 .

Output

For each test case you have to output a single integer on a separate line: the number of knights that have to be expelled.

Sample Input

5 5
1 4
1 5
2 5
3 4
4 5
0 0

Sample Output

Hint

Huge input file, 'scanf' recommended to avoid TLE.

Source

Central Europe 2005

题目类型：反向构图+求解重连通分量(点)+交叉染色判奇圈

算法分析：首先构造图，把武士看作是顶点，若两个武士之间没有相互仇视，则在两个顶点之间连边，表示两个武士可以在一个圆桌旁相邻就坐。要让武士在一个圈内才能满足要求，不在圈内的武士会被剔除掉。所以这个时候求解这个图的重连通分量(点)，构造满足条件的环。此时只要判断这个环是奇圈即可，这里使用交叉染色的方法判定(由一个判奇圈的充要条件得来)。注意：构造出来的图有可能是非连通图！！！

/*************************************************
Author        :supermaker
Created Time  :2016/1/21 18:40:28
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1000 + 66;

int g[maxn][maxn], vis[maxn], dfsn[maxn], low[maxn], color[maxn], part[maxn], res[maxn];
int n, m, id;
stack <PII> sta;

void Init (int rt)
{
	vis[rt] = 1;
	dfsn[rt] = low[rt] = id = 1;
	while (!sta.empty ()) sta.pop ();
}

bool CrossColor (int u, int col)
{
	color[u] = col;
	for (int v = 1; v <= n; v++)
		if (g[u][v] && part[v])//it is possible : g[u][v] == 2 || g[u][v] == 1
		{
			if (color[v] == 0 && CrossColor (v, -col)) return 1;
			if (color[v] == col) return 1;
		}
	return 0;
}

void SS ()
{
	for (int i = 1; i <= n; i++)
		if (part[i])
		{
			memset (color, 0, sizeof (color));
			if (CrossColor (i, 1))
				for (int j = 1; j <= n; j++)
					if (part[j])
						res[j]++;
			return ;
		}
}

void dfs (int u, int par)
{
	for (int v = 1; v <= n; v++)
	{
		if (g[u][v] == 1)
		{
			sta.push (PII (u, v));
			g[u][v] = g[v][u] = 2;
			if (!vis[v])
			{
				vis[v] = 1;
				dfsn[v] = low[v] = ++id;
				dfs (v, u);
				low[u] = min (low[u], low[v]);
				if (low[v] >= dfsn[u])
				{
					memset (part, 0, sizeof (part));
					while (!sta.empty ())
					{
						PII temp = sta.top (); sta.pop ();
						part[temp.first] = part[temp.second] = 1;	
						//printf (" %d-%d ", temp.first, temp.second);
						if ((temp.first == u && temp.second == v) || (temp.first == v && temp.second == u))
							break;	
					}
					//puts ("");
					SS ();
				}
			}
			else if (v != par)
				low[u] = min (low[u], dfsn[v]);
		}
	}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		if (n == 0 && m == 0) break;

		memset (res, 0, sizeof (res));
		memset (vis, 0, sizeof (vis));
		for (int i = 0; i < maxn; i++)
			for (int j = 0; j < maxn; j++)
			{
				if (i == j) g[i][j] = 0;//important!!!
				else g[i][j] = 1;
			}

		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			g[u][v] = g[v][u] = 0;
		}

		for (int i = 1; i <= n; i++)
			if (!vis[i])
			{
				Init (i);
				dfs (i, -1);
			}
		int ans = 0;
		for (int i = 1; i <= n; i++)
			if (!res[i]) 
				ans++;

		printf ("%d\n", ans);
	}
    return 0;
}

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

/*************************************************

Author :supermaker

Created Time :2016/1/21 18:40:28

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1000 + 66;

int g[maxn][maxn], vis[maxn], dfsn[maxn], low[maxn], color[maxn], part[maxn], res[maxn];

int n, m, id;

stack <PII> sta;

void Init (int rt)

{

vis[rt] = 1;

dfsn[rt] = low[rt] = id = 1;

while (!sta.empty ()) sta.pop ();

}

bool CrossColor (int u, int col)

{

color[u] = col;

for (int v = 1; v <= n; v++)

if (g[u][v] && part[v])//it is possible : g[u][v] == 2 || g[u][v] == 1

{

if (color[v] == 0 && CrossColor (v, -col)) return 1;

if (color[v] == col) return 1;

}

return 0;

}

void SS ()

{

for (int i = 1; i <= n; i++)

if (part[i])

{

memset (color, 0, sizeof (color));

if (CrossColor (i, 1))

for (int j = 1; j <= n; j++)

if (part[j])

res[j]++;

return ;

}

void dfs (int u, int par)

{

for (int v = 1; v <= n; v++)

{

if (g[u][v] == 1)

{

sta.push (PII (u, v));

g[u][v] = g[v][u] = 2;

if (!vis[v])

{

vis[v] = 1;

dfsn[v] = low[v] = ++id;

dfs (v, u);

low[u] = min (low[u], low[v]);

if (low[v] >= dfsn[u])

{

memset (part, 0, sizeof (part));

while (!sta.empty ())

{

PII temp = sta.top (); sta.pop ();

part[temp.first] = part[temp.second] = 1;

//printf (" %d-%d ", temp.first, temp.second);

if ((temp.first == u && temp.second == v) || (temp.first == v && temp.second == u))

break;

}

//puts ("");

SS ();

}

else if (v != par)

low[u] = min (low[u], dfsn[v]);

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &m) != EOF)

{

if (n == 0 && m == 0) break;

memset (res, 0, sizeof (res));

memset (vis, 0, sizeof (vis));

for (int i = 0; i < maxn; i++)

for (int j = 0; j < maxn; j++)

{

if (i == j) g[i][j] = 0;//important!!!

else g[i][j] = 1;

}

for (int i = 1; i <= m; i++)

{

int u, v;

scanf ("%d%d", &u, &v);

g[u][v] = g[v][u] = 0;

}

for (int i = 1; i <= n; i++)

if (!vis[i])

{

Init (i);

dfs (i, -1);

}

int ans = 0;

for (int i = 1; i <= n; i++)

if (!res[i])

ans++;

printf ("%d\n", ans);

}

return 0;

}

zoj2588

maksyuki 发表于 oj 分类，标签: 图论-求解割点\割边(Tarjan)

21 1月 2016

Burning Bridges

Ferry Kingdom is a nice little country located on N islands that are connected by M bridges. All bridges are very beautiful and are loved by everyone in the kingdom. Of course, the system of bridges is designed in such a way that one can get from any island to any other one.

But recently the great sorrow has come to the kingdom. Ferry Kingdom was conquered by the armies of the great warrior Jordan and he has decided to burn all the bridges that connected the islands. This was a very cruel decision, but the wizards of Jordan have advised him no to do so, because after that his own armies would not be able to get from one island to another. So Jordan decided to burn as many bridges as possible so that is was still possible for his armies to get from any island to any other one.

Now the poor people of Ferry Kingdom wonder what bridges will be burned. Of course, they cannot learn that, because the list of bridges to be burned is kept in great secret. However, one old man said that you can help them to find the set of bridges that certainly will not be burned.

So they came to you and asked for help. Can you do that?

Input

The input contains multiple test cases. The first line of the input is a single integer T (1 <= T <= 20) which is the number of test cases. T test cases follow, each preceded by a single blank line.

The first line of each case contains N and M - the number of islands and bridges in Ferry Kingdom respectively (2 <= N <= 10 000, 1 <= M <= 100 000). Next M lines contain two different integer numbers each and describe bridges. Note that there can be several bridges between a pair of islands.

Output

On the first line of each case print K - the number of bridges that will certainly not be burned. On the second line print K integers - the numbers of these bridges. Bridges are numbered starting from one, as they are given in the input.

Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

Sample Input

6 7

1 2

2 3

2 4

5 4

1 3

4 5

3 6

10 16

2 6

3 7

6 5

5 9

5 4

1 2

9 8

6 4

2 10

3 8

7 9

1 4

2 4

10 5

1 6

6 10

Sample Output

3 7

Author: Andrew Stankevich

Source: Andrew Stankevich's Contest #5

题目类型：求解割边(可能有重边) Tarjan

算法分析：求解割边的过程和求解割点的类似，只是满足：low[v] > dfsn[u]，u是v的父节点。若图中存在重边，则直接特判即可，注意输出的格式

/*************************************************
Author        :supermaker
Created Time  :2016/1/21 13:05:23
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 10000 + 66;

int vis[maxn], dfsn[maxn], low[maxn], out[maxn*10];
int n, m, id, len;
map <PII, int> overedge;
vector <PII> edge[maxn*10];

void Init (int rt)
{
	overedge.clear ();
	for (int i = 0; i < maxn * 10; i++)
		edge[i].clear ();
	dfsn[rt] = low[rt] = id = 1;
	memset (vis, 0, sizeof (vis));
	vis[rt] = 1;
	len = 0;
}

void dfs (int u, int par)
{
	for (int i = 0; i < edge[u].size (); i++)
	{
		int v = edge[u][i].first;
		if (!vis[v])
		{
			vis[v] = 1;
			dfsn[v] = low[v] = ++id;
			dfs (v, u);
			low[u] = min (low[u], low[v]);
			if (low[v] > dfsn[u] && overedge[PII(u,v)] == 1)
				out[++len] = edge[u][i].second;
		}

		else if (v != par)
			low[u] = min (low[u], dfsn[v]);
	}
}

int main()
{
    //CFF;
    //CPPFF;
	int t, flag = 1;
	scanf ("%d", &t);
	while (t--)
	{
		if (flag++ > 1) puts ("");
		scanf ("%d%d", &n, &m);

		Init (1);
		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			edge[u].push_back (PII (v, i));
			edge[v].push_back (PII (u, i));
			if (overedge.find (PII (u, v)) == overedge.end ())
				overedge[PII(u,v)] = overedge[PII(v,u)] = 1;

			else
				overedge[PII(u,v)]++, overedge[PII(v,u)]++;
		}

		dfs (1, -1);

		printf ("%d\n", len);
		sort (out + 1, out + 1 + len);
		for (int i = 1; i <= len; i++)
		{
			if (i == 1) printf ("%d", out[i]);
			else printf (" %d", out[i]);
		}
		if (len) puts ("");
	}
    return 0;
}

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

/*************************************************

Author :supermaker

Created Time :2016/1/21 13:05:23

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 10000 + 66;

int vis[maxn], dfsn[maxn], low[maxn], out[maxn*10];

int n, m, id, len;

map <PII, int> overedge;

vector <PII> edge[maxn*10];

void Init (int rt)

{

overedge.clear ();

for (int i = 0; i < maxn * 10; i++)

edge[i].clear ();

dfsn[rt] = low[rt] = id = 1;

memset (vis, 0, sizeof (vis));

vis[rt] = 1;

len = 0;

}

void dfs (int u, int par)

{

for (int i = 0; i < edge[u].size (); i++)

{

int v = edge[u][i].first;

if (!vis[v])

{

vis[v] = 1;

dfsn[v] = low[v] = ++id;

dfs (v, u);

low[u] = min (low[u], low[v]);

if (low[v] > dfsn[u] && overedge[PII(u,v)] == 1)

out[++len] = edge[u][i].second;

}

else if (v != par)

low[u] = min (low[u], dfsn[v]);

}

int main()

{

//CFF;

//CPPFF;

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

if (flag++ > 1) puts ("");

scanf ("%d%d", &n, &m);

Init (1);

for (int i = 1; i <= m; i++)

{

int u, v;

scanf ("%d%d", &u, &v);

edge[u].push_back (PII (v, i));

edge[v].push_back (PII (u, i));

if (overedge.find (PII (u, v)) == overedge.end ())

overedge[PII(u,v)] = overedge[PII(v,u)] = 1;

else

overedge[PII(u,v)]++, overedge[PII(v,u)]++;

}

dfs (1, -1);

printf ("%d\n", len);

sort (out + 1, out + 1 + len);

for (int i = 1; i <= len; i++)

{

if (i == 1) printf ("%d", out[i]);

else printf (" %d", out[i]);

}

if (len) puts ("");

}

return 0;

}

poj1043

maksyuki 发表于 oj 分类，标签: 图论-二分图最大匹配

20 1月 2016

What's In A Name?

The FBI is conducting a surveillance of a known criminal hideout which serves as a communication center for a number of men and women of nefarious intent. Using sophisticated decryption software and good old fashion wiretaps, they are able to decode any e-mail messages leaving the site. However, before any arrest warrants can be served, they must match actual names with the user ID's on the messages. While these criminals are evil, they're not stupid, so they use random strings of letters for
their ID's (no dillingerj ID's found here). The FBI knows that each criminal uses only one ID. The only other information they have which will help them is a log of names of the people who enter and leave the hideout. In many cases, this is enough to link the names to the ID's.

Input

Input consists of one problem instance. The first line contains a single positive integer n indicating the number of criminals using the hideout. The maximum value for n will be 20. The next line contains the n user ID's, separated by single spaces. Next will be the log entries in chronological order. Each entry in the log has the form type arg , where type is either E, L or M: E indicates that criminal arg has entered the hideout; L indicates criminal arg has left the hideout; M indicates a message was intercepted from user ID arg. A line containing only the letter Q indicates the end of the log. Note that not all user ID's may be present in the log but each criminal name will be guaranteed to be in the log at least once. At the start of the log, the hideout is presumed to be empty. All names and user ID's consist of only lowercase letters and have length at most 20. Note: The line containing only the user ID's may contain more than 80 characters.

Output

Output consists of n lines, each containing a list of criminal names and their corresponding user ID's, if known. The list should be sorted in alphabetical order by the criminal names. Each line has the form name:userid , where name is the criminal's name and userid is either their user ID or the string ??? if their user ID could not be determined from the surveillance log.

Sample Input

7
bigman mangler sinbad fatman bigcheese frenchie capodicapo
E mugsy
E knuckles
M bigman
M mangler
L mugsy
E clyde
E bonnie
M bigman
M fatman
M frenchie
L clyde
M fatman
E ugati
M sinbad
E moriarty
E booth
Q

Sample Output

bonnie:fatman
booth:???
clyde:frenchie
knuckles:bigman
moriarty:???
mugsy:mangler
ugati:sinbad

Source

East Central North America 2001

题目类型：反向构图+删边判断+二分图最大匹配

算法分析：首先这个图明显是一个二分图，这里构造二分图时使用了一个巧妙的方法：反向构造。即先在所有姓名-用户名对之间连边，然后每次在得到邮件信息(比如用户名a)时，将不在藏匿点的姓名和用户名a之间的边删去，最后就留下所有可能的情况。然后枚举每条边并将其删去，判断得到的最大匹配数是否小于没删去之前的最大匹配数。若小于，则说明当前边是一个唯一确定的边。否则当前边是目前还未确定的(注意只是目前还未确定的，有可能之后被唯一确定)

/*************************************************
Author        :supermaker
Created Time  :2016/1/20 14:39:00
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 66;

string sa[maxn], sb[maxn], cmda[maxn*maxn], cmdb[maxn*maxn];
int g[maxn][maxn], vis[maxn];
int cx[maxn], cy[maxn], cxlen, cylen;

int dfs (int u)
{
	for (int v = 1; v <= cylen; v++)
		if (g[u][v] < INF && !vis[v])
		{
			vis[v] = 1;
			if (cy[v] == -1 || dfs (cy[v]))
			{
				cy[v] = u;
				cx[u] = v;
				return 1;
			}
		}
	return 0;
}

int maxmatch ()
{
	int res = 0;
	memset (cx, -1, sizeof (cx));
	memset (cy, -1, sizeof (cy));
	for (int i = 1; i <= cxlen; i++)
		if (cx[i] == -1)
		{
			memset (vis, 0, sizeof (vis));
			res += dfs (i);
		}
	return res;
}

int main()
{
    //CFF;
    //CPPFF;
	int n;
	while (cin >> n)
	{
		for (int i = 1; i <= n; i++)
			cin >> sa[i];

		int len = 0;
		string tempa, tempb;
		set <string> seta;
		cxlen = cylen = 0;
		while (cin >> tempa)
		{
			if (tempa == "Q") break;
			cin >> tempb;
			len++;
			cmda[len] = tempa, cmdb[len] = tempb;
			if (tempa != "M" && seta.find (tempb) == seta.end ())
			{
				seta.insert (tempb);
				sb[++cylen] = tempb;
			}
		}
		
		cxlen = n;
	//	DB (cxlen), DB (cylen);
		for (int i = 1; i <= cxlen; i++)
			for (int j = 1; j <= cylen; j++)
				g[i][j] = 1;
	
		seta.clear ();
		for (int i = 1; i <= len; i++)
		{
			if (cmda[i] == "E") 
				seta.insert (cmdb[i]);

			else if (cmda[i] == "L")
				seta.erase (cmdb[i]);

			else if (cmda[i] == "M")
			{
				int pos = 1;
				for (int j = 1; j <= cxlen; j++)
					if (sa[j] == cmdb[i])
					{
						pos = j;
						break;
					}
				for (int j = 1; j <= cylen; j++)
					if (seta.find (sb[j]) == seta.end ())
						g[pos][j] = INF;
			}
		}
		

		map <string, string> ans;
		int org = maxmatch ();
		for (int i = 1; i <= cxlen; i++)
			for (int j = 1; j <= cylen; j++)
				if (g[i][j] == 1)
				{
					g[i][j] = INF;
					int tt = maxmatch ();
					g[i][j] = 1;
					if (ans.find (sb[j]) != ans.end () && ans[sb[j]] != "???") continue;

					if (tt < org)
						ans[sb[j]] = sa[i];	

					else
						ans[sb[j]] = "???";
				//	DB (i), DB (j), DB (tt), DB (sb[j]), DB (sa[i]), DB (ans[sb[j]]), cout << endl;
				}

		for (map <string, string> :: iterator it = ans.begin (); it != ans.end (); it++)
			cout << it -> first << ":" << it -> second << endl;
		//cout << endl;
	}
    return 0;
}

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

/*************************************************

Author :supermaker

Created Time :2016/1/20 14:39:00

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 66;

string sa[maxn], sb[maxn], cmda[maxn*maxn], cmdb[maxn*maxn];

int g[maxn][maxn], vis[maxn];

int cx[maxn], cy[maxn], cxlen, cylen;

int dfs (int u)

{

for (int v = 1; v <= cylen; v++)

if (g[u][v] < INF && !vis[v])

{

vis[v] = 1;

if (cy[v] == -1 || dfs (cy[v]))

{

cy[v] = u;

cx[u] = v;

return 1;

}

return 0;

}

int maxmatch ()

{

int res = 0;

memset (cx, -1, sizeof (cx));

memset (cy, -1, sizeof (cy));

for (int i = 1; i <= cxlen; i++)

if (cx[i] == -1)

{

memset (vis, 0, sizeof (vis));

res += dfs (i);

}

return res;

}

int main()

{

//CFF;

//CPPFF;

int n;

while (cin >> n)

{

for (int i = 1; i <= n; i++)

cin >> sa[i];

int len = 0;

string tempa, tempb;

set <string> seta;

cxlen = cylen = 0;

while (cin >> tempa)

{

if (tempa == "Q") break;

cin >> tempb;

len++;

cmda[len] = tempa, cmdb[len] = tempb;

if (tempa != "M" && seta.find (tempb) == seta.end ())

{

seta.insert (tempb);

sb[++cylen] = tempb;

}

cxlen = n;

// DB (cxlen), DB (cylen);

for (int i = 1; i <= cxlen; i++)

for (int j = 1; j <= cylen; j++)

g[i][j] = 1;

seta.clear ();

for (int i = 1; i <= len; i++)

{

if (cmda[i] == "E")

seta.insert (cmdb[i]);

else if (cmda[i] == "L")

seta.erase (cmdb[i]);

else if (cmda[i] == "M")

{

int pos = 1;

for (int j = 1; j <= cxlen; j++)

if (sa[j] == cmdb[i])

{

pos = j;

break;

}

for (int j = 1; j <= cylen; j++)

if (seta.find (sb[j]) == seta.end ())

g[pos][j] = INF;

}

map <string, string> ans;

int org = maxmatch ();

for (int i = 1; i <= cxlen; i++)

for (int j = 1; j <= cylen; j++)

if (g[i][j] == 1)

{

g[i][j] = INF;

int tt = maxmatch ();

g[i][j] = 1;

if (ans.find (sb[j]) != ans.end () && ans[sb[j]] != "???") continue;

if (tt < org)

ans[sb[j]] = sa[i];

else

ans[sb[j]] = "???";

// DB (i), DB (j), DB (tt), DB (sb[j]), DB (sa[i]), DB (ans[sb[j]]), cout << endl;

}

for (map <string, string> :: iterator it = ans.begin (); it != ans.end (); it++)

cout << it -> first << ":" << it -> second << endl;

//cout << endl;

}

return 0;

}

poj3041

maksyuki 发表于 oj 分类，标签: 图论-二分图最大匹配, 图论-最小点覆盖

20 1月 2016

Asteroids

Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.

Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.

Input

* Line 1: Two integers N and K, separated by a single space.
* Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.

Output

* Line 1: The integer representing the minimum number of times Bessie must shoot.

Sample Input

3 4
1 1
1 3
2 2
3 2

Sample Output

Hint

INPUT DETAILS:
The following diagram represents the data, where "X" is an asteroid and "." is empty space:
X.X
.X.
.X.

OUTPUT DETAILS:
Bessie may fire across row 1 to destroy the asteroids at (1,1) and (1,3), and then she may fire down column 2 to destroy the asteroids at (2,2) and (3,2).

Source

USACO 2005 November Gold

题目类型：最小点覆盖(二分图最大匹配)

算法分析：首先要对原图进行一个转化，将每行中的行星看做是在一个块中并标号，每列中的行星看做是在一个块中并标号，每个块中最多只需一个子弹就可以全部消灭行星。然后将横块和竖块中重合的块之间连线，这样原图就转化成一个等效的二分图。现在等效求解用多少点(块)来“覆盖”边，使得所有的边都被覆盖到。这样直接求解最大匹配即可

/*************************************************
Author        :supermaker
Created Time  :2016/1/20 12:46:45
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 500 + 66;

int xs[maxn][maxn], ys[maxn][maxn];
bool g[maxn][maxn], vis[maxn*maxn], gg[maxn][maxn];
int cx[maxn*maxn], cy[maxn*maxn], cxlen, cylen;

int dfs (int u)
{
	for (int v = 1; v <= cylen; v++)
		if (g[u][v] && !vis[v])
		{
			vis[v] = true;
			if (cy[v] == -1 || dfs (cy[v]))
			{
				cy[v] = u;
				cx[u] = v;
				return 1;
			}
		}
	return 0;
}

int maxmatch ()
{
	int res = 0;
	memset (cx, -1, sizeof (cx));
	memset (cy, -1, sizeof (cy));
	for (int i = 1; i <= cxlen; i++)
		if (cx[i] == -1)
		{
			memset (vis, false, sizeof (vis));
			res += dfs (i);
		}
	return res;
}

int main()
{
    //CFF;
    //CPPFF;
   	int n, k;
	while (scanf ("%d%d", &n, &k) != EOF)
	{
		memset (gg, false, sizeof (gg));
		memset (g, false, sizeof (g));
		memset (xs, 0, sizeof (xs));
		memset (ys, 0, sizeof (ys));
		for (int i = 1; i <= k; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			gg[u][v] = true;		
		}
	
		cxlen = 0;
		for (int i = 1; i <= n; i++)
		{
			bool is_first = true;
			for (int j = 1; j <= n; j++)
				if (gg[i][j])
				{
					if (is_first)
					{
						is_first = false;
						xs[i][j] = ++cxlen;
					}
					else
						xs[i][j] = cxlen;
				}	
		}

		cylen = 0;
		for (int i = 1; i <= n; i++)
		{
			bool is_first = true;
			for (int j = 1; j <= n; j++)
				if (gg[j][i])
				{
					if (is_first)
					{
						is_first = false;
						ys[j][i] = ++cylen;
					}
					else
						ys[j][i] = cylen;	
				}
		}
		
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (xs[i][j])
					g[xs[i][j]][ys[i][j]] = true;
		
		printf ("%d\n", maxmatch ());
	}
    return 0;
}

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

/*************************************************

Author :supermaker

Created Time :2016/1/20 12:46:45

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 500 + 66;

int xs[maxn][maxn], ys[maxn][maxn];

bool g[maxn][maxn], vis[maxn*maxn], gg[maxn][maxn];

int cx[maxn*maxn], cy[maxn*maxn], cxlen, cylen;

int dfs (int u)

{

for (int v = 1; v <= cylen; v++)

if (g[u][v] && !vis[v])

{

vis[v] = true;

if (cy[v] == -1 || dfs (cy[v]))

{

cy[v] = u;

cx[u] = v;

return 1;

}

return 0;

}

int maxmatch ()

{

int res = 0;

memset (cx, -1, sizeof (cx));

memset (cy, -1, sizeof (cy));

for (int i = 1; i <= cxlen; i++)

if (cx[i] == -1)

{

memset (vis, false, sizeof (vis));

res += dfs (i);

}

return res;

}

int main()

{

//CFF;

//CPPFF;

int n, k;

while (scanf ("%d%d", &n, &k) != EOF)

{

memset (gg, false, sizeof (gg));

memset (g, false, sizeof (g));

memset (xs, 0, sizeof (xs));

memset (ys, 0, sizeof (ys));

for (int i = 1; i <= k; i++)

{

int u, v;

scanf ("%d%d", &u, &v);

gg[u][v] = true;

}

cxlen = 0;

for (int i = 1; i <= n; i++)

{

bool is_first = true;

for (int j = 1; j <= n; j++)

if (gg[i][j])

{

if (is_first)

{

is_first = false;

xs[i][j] = ++cxlen;

}

else

xs[i][j] = cxlen;

}

cylen = 0;

for (int i = 1; i <= n; i++)

{

bool is_first = true;

for (int j = 1; j <= n; j++)

if (gg[j][i])

{

if (is_first)

{

is_first = false;

ys[j][i] = ++cylen;

}

else

ys[j][i] = cylen;

}

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

if (xs[i][j])

g[xs[i][j]][ys[i][j]] = true;

printf ("%d\n", maxmatch ());

}

return 0;

}

poj1422

maksyuki 发表于 oj 分类，标签: 图论-二分图最大匹配, 图论-最小路径覆盖

20 1月 2016

Air Raid

Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles.

With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper.

Input

Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:

no_of_intersections
no_of_streets
S1 E1
S2 E2
......
Sno_of_streets Eno_of_streets

The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town's streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections.

There are no blank lines between consecutive sets of data. Input data are correct.

Output

The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town.

Sample Input

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

Sample Output

Source

Dhaka 2002

题目类型：最小路径覆盖(二分图最大匹配)

算法分析：这是一道典型的最小路径覆盖问题，最小路径覆盖数等于顶点数减去最大匹配数。首先将每个点拆成两个点，然后在一边的点和另一边的点之间连一条边(有向边)。最后在这个二分图上跑一个最大匹配即可

/*************************************************
Author        :supermaker
Created Time  :2016/1/20 10:43:02
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 666 + 66;

int g[maxn][maxn], vis[maxn];
int cx[maxn], cy[maxn], cxlen, cylen;

int dfs (int u)
{
	for (int v = 1; v <= cylen; v++)
		if (g[u][v] < INF && !vis[v])
		{
			vis[v] = 1;
			if (cy[v] == -1 || dfs (cy[v]))
			{
				cy[v] = u;
				cx[u] = v;
				return 1;
			}
		}
	return 0;
}

int maxmatch ()
{
	int res = 0;
	memset (cx, -1, sizeof (cx));
	memset (cy, -1, sizeof (cy));
	for (int i = 1; i <= cxlen; i++)
		if (cx[i] == -1)
		{
			memset (vis, 0, sizeof (vis));
			res += dfs (i);
		}
	return res;
}

int main()
{
    //CFF;
    //CPPFF;
	int t;
	scanf ("%d", &t);
	while (t--)
	{
		int n;
		scanf ("%d", &n);
		for (int i = 0; i < maxn; i++)
			for (int j = 0; j < maxn; j++)
				g[i][j] = INF;

		int m;
		scanf ("%d", &m);
		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			g[u][v] = 1;
		}

		cxlen = cylen = n;
		printf ("%d\n", n - maxmatch ());
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

/*************************************************

Author :supermaker

Created Time :2016/1/20 10:43:02

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 666 + 66;

int g[maxn][maxn], vis[maxn];

int cx[maxn], cy[maxn], cxlen, cylen;

int dfs (int u)

{

for (int v = 1; v <= cylen; v++)

if (g[u][v] < INF && !vis[v])

{

vis[v] = 1;

if (cy[v] == -1 || dfs (cy[v]))

{

cy[v] = u;

cx[u] = v;

return 1;

}

return 0;

}

int maxmatch ()

{

int res = 0;

memset (cx, -1, sizeof (cx));

memset (cy, -1, sizeof (cy));

for (int i = 1; i <= cxlen; i++)

if (cx[i] == -1)

{

memset (vis, 0, sizeof (vis));

res += dfs (i);

}

return res;

}

int main()

{

//CFF;

//CPPFF;

int t;

scanf ("%d", &t);

while (t--)

{

int n;

scanf ("%d", &n);

for (int i = 0; i < maxn; i++)

for (int j = 0; j < maxn; j++)

g[i][j] = INF;

int m;

scanf ("%d", &m);

for (int i = 1; i <= m; i++)

{

int u, v;

scanf ("%d%d", &u, &v);

g[u][v] = 1;

}

cxlen = cylen = n;

printf ("%d\n", n - maxmatch ());

}

return 0;

}

poj1466

maksyuki 发表于 oj 分类，标签: 图论-二分图最大匹配, 图论-最大点独立

20 1月 2016

Girls and Boys

In the second year of the university somebody started a study on the romantic relations between the students. The relation "romantically involved" is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been "romantically involved". The result of the program is the number of students in such a set.

Input

The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description:

the number of students
the description of each student, in the following format
student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ...
or
student_identifier:(0)

The student_identifier is an integer number between 0 and n-1 (n <=500 ), for n subjects.

Output

For each given data set, the program should write to standard output a line containing the result.

Sample Input

7
0: (3) 4 5 6
1: (2) 4 6
2: (0)
3: (0)
4: (2) 0 1
5: (1) 0
6: (2) 0 1
3
0: (2) 1 2
1: (1) 0
2: (1) 0

Sample Output

Source

Southeastern Europe 2000

题目类型：最大点独立集(二分图最大匹配)

算法分析：这里给出n个点和m条边，求解最大的点独立集是多少，这里使用基于网络流的算法会比使用匈牙利算法要简单

/*************************************************
Author        :supermaker
Created Time  :2016/1/19 20:35:16
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 500 + 66;

int match[maxn], vis[maxn];
vector <int> g[maxn];
int n;

int dfs (int u)
{
	vis[u] = true;
	for (int i = 0; i < g[u].size (); i++)
	{
		int v = g[u][i], t = match[v];
		if (t < 0 || (!vis[t] && dfs (t)))
		{
			match[u] = v;
			match[v] = u;
			return 1; 
		}
	}
	return 0;
}

int maxmatch ()
{
	int res = 0;
	memset (match, -1, sizeof (match));
	for (int i = 0; i < n; i++)
		if (match[i] == -1)
		{
			memset (vis, 0, sizeof (vis));
			res += dfs (i);
		}
	return res;
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{	
		for (int i = 0; i < maxn; i++) g[i].clear ();

		for (int i = 1; i <= n; i++)
		{
			int vala, num;
			scanf ("%d: (%d) ", &vala, &num);
			int valb;
			for (int j = 1; j <= num; j++)
			{
				scanf ("%d", &valb);
				g[vala].push_back (valb);
			}
		}
		
		printf ("%d\n", n - maxmatch ());
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

/*************************************************

Author :supermaker

Created Time :2016/1/19 20:35:16

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 500 + 66;

int match[maxn], vis[maxn];

vector <int> g[maxn];

int n;

int dfs (int u)

{

vis[u] = true;

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i], t = match[v];

if (t < 0 || (!vis[t] && dfs (t)))

{

match[u] = v;

match[v] = u;

return 1;

}

return 0;

}

int maxmatch ()

{

int res = 0;

memset (match, -1, sizeof (match));

for (int i = 0; i < n; i++)

if (match[i] == -1)

{

memset (vis, 0, sizeof (vis));

res += dfs (i);

}

return res;

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d", &n) != EOF)

{

for (int i = 0; i < maxn; i++) g[i].clear ();

for (int i = 1; i <= n; i++)

{

int vala, num;

scanf ("%d: (%d) ", &vala, &num);

int valb;

for (int j = 1; j <= num; j++)

{

scanf ("%d", &valb);

g[vala].push_back (valb);

}

printf ("%d\n", n - maxmatch ());

}

return 0;

}

zoj1654

maksyuki 发表于 oj 分类，标签: 图论-二分图最大匹配

19 1月 2016

Place the Robots

Robert is a famous engineer. One day he was given a task by his boss. The background of the task was the following: Given a map consisting of square blocks. There were three kinds of blocks: Wall, Grass, 阅读全文 »

hdu4417

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举, 数据结构-划分树

15 1月 2016

Super Mario

Problem Description

Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is 阅读全文 »

hdu4251

maksyuki 发表于 oj 分类，标签: 数据结构-划分树

14 1月 2016

The Famous ICPC Team Again

Problem Description

When Mr. B, Mr. G and Mr. M were preparing for the 2012 ACM-ICPC World Final Contest, Mr. B had collected a large set of contest problems for their daily training. When they decided to take training, Mr. B would choose one of them from the problem set. All the problems in the problem set had been sorted by their time of publish. Each time Prof. S, their coach, would tell them to choose one problem published within a particular time interval. That is to say, if problems had been sorted in a line, each time they would choose one of them from a specified segment of the line.

Moreover, when collecting the problems, Mr. B had also known an estimation of each problem’s difficultness. When he was asked to choose a problem, if he chose the easiest one, Mr. G would complain that “Hey, what a trivial problem!”; if he chose the hardest one, Mr. M would grumble that it took too much time to finish it. To address this dilemma, Mr. B decided to take the one with the medium difficulty. Therefore, he needed a way to know the median number in the given interval of the sequence.

Input

For each test case, the first line contains a single integer n (1 <= n <= 100,000) indicating the total number of problems. The second line contains n integers xi (0 <= xi <= 1,000,000,000), separated by single space, denoting the difficultness of each problem, already sorted by publish time. The next line contains a single integer m (1 <= m <= 100,000), specifying number of queries. Then m lines follow, each line contains a pair of integers, A and B (1 <= A <= B <= n), denoting that Mr. B needed to choose a problem between positions A and B (inclusively, positions are counted from 1). It is guaranteed that the number of items between A and B is odd.

Output

For each query, output a single line containing an integer that denotes the difficultness of the problem that Mr. B should choose.

Sample Input

5
5 3 2 4 1
3
1 3
2 4
3 5
5
10 6 4 8 2
3
1 3
2 4
3 5

Sample Output

Case 1:

Case 2:

Source

Fudan Local Programming Contest 2012

题目类型：划分树

算法分析：划分树的简单应用，每次查询的是区间第(区间元素个数tot+1) / 2大的元素

/*************************************************
Author        :supermaker
Created Time  :2016/1/14 23:07:29
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int sorted[maxn], tree[30][maxn], toleft[30][maxn];

void build (int dep, int l, int r)
{
	if (l == r) return ;
	int mid = (l + r) >> 1;
	int same = mid - l + 1;
	for (int i = l; i <= r; i++)
		if (tree[dep][i] < sorted[mid])
			same--;
	
	int lpos = l, rpos = mid + 1;
	for (int i = l; i <= r; i++)
	{
		if (tree[dep][i] < sorted[mid]) 
			tree[dep+1][lpos++] = tree[dep][i];

		else if (tree[dep][i] == sorted[mid] && same > 0)
		{
			tree[dep+1][lpos++] = tree[dep][i];
			same--;
		}

		else
			tree[dep+1][rpos++] = tree[dep][i];
	
		toleft[dep][i] = toleft[dep][l-1] + (lpos - l);
	}
	build (dep + 1, l, mid);
	build (dep + 1, mid + 1, r);
}

int query (int dep, int L, int R, int l, int r, int k)
{
	if (l == r) return tree[dep][l];
	int mid = (L + R) >> 1;
	int tot = toleft[dep][r] - toleft[dep][l-1];
	if (tot >= k)
	{
		int newl = L + toleft[dep][l-1] - toleft[dep][L-1];
		int newr = newl + tot - 1;
		return query (dep + 1, L, mid, newl, newr, k);
	}
	else
	{
		int newr = r + toleft[dep][R] - toleft[dep][r];
		int newl = newr - (r - l - tot);
		return query (dep + 1, mid + 1, R, newl, newr, k - tot);
	}
}

int main()
{
    //CFF;
    //CPPFF;
	int n, flag = 1;
	while (scanf ("%d", &n) != EOF)
	{
		memset (tree, 0, sizeof (tree));
		memset (toleft, 0, sizeof (toleft));
		for (int i = 1; i <= n; i++)
		{
			scanf ("%d", &tree[0][i]);
			sorted[i] = tree[0][i];
		}
		sort (sorted + 1, sorted + 1 + n);
		
		printf ("Case %d:\n", flag++);
		build (0, 1, n);
		int q;
		scanf ("%d", &q);
		for (int i = 1; i <= q; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			int tot = v - u + 1;
			tot = (tot + 1) / 2;
			printf ("%d\n", query (0, 1, n, u, v, tot));
		}
	}
    return 0;
}

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

/*************************************************

Author :supermaker

Created Time :2016/1/14 23:07:29

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int sorted[maxn], tree[30][maxn], toleft[30][maxn];

void build (int dep, int l, int r)

{

if (l == r) return ;

int mid = (l + r) >> 1;

int same = mid - l + 1;

for (int i = l; i <= r; i++)

if (tree[dep][i] < sorted[mid])

same--;

int lpos = l, rpos = mid + 1;

for (int i = l; i <= r; i++)

{

if (tree[dep][i] < sorted[mid])

tree[dep+1][lpos++] = tree[dep][i];

else if (tree[dep][i] == sorted[mid] && same > 0)

{

tree[dep+1][lpos++] = tree[dep][i];

same--;

}

else

tree[dep+1][rpos++] = tree[dep][i];

toleft[dep][i] = toleft[dep][l-1] + (lpos - l);

}

build (dep + 1, l, mid);

build (dep + 1, mid + 1, r);

}

int query (int dep, int L, int R, int l, int r, int k)

{

if (l == r) return tree[dep][l];

int mid = (L + R) >> 1;

int tot = toleft[dep][r] - toleft[dep][l-1];

if (tot >= k)

{

int newl = L + toleft[dep][l-1] - toleft[dep][L-1];

int newr = newl + tot - 1;

return query (dep + 1, L, mid, newl, newr, k);

}

else

{

int newr = r + toleft[dep][R] - toleft[dep][r];

int newl = newr - (r - l - tot);

return query (dep + 1, mid + 1, R, newl, newr, k - tot);

}

int main()

{

//CFF;

//CPPFF;

int n, flag = 1;

while (scanf ("%d", &n) != EOF)

{

memset (tree, 0, sizeof (tree));

memset (toleft, 0, sizeof (toleft));

for (int i = 1; i <= n; i++)

{

scanf ("%d", &tree[0][i]);

sorted[i] = tree[0][i];

}

sort (sorted + 1, sorted + 1 + n);

printf ("Case %d:\n", flag++);

build (0, 1, n);

int q;

scanf ("%d", &q);

for (int i = 1; i <= q; i++)

{

int u, v;

scanf ("%d%d", &u, &v);

int tot = v - u + 1;

tot = (tot + 1) / 2;

printf ("%d\n", query (0, 1, n, u, v, tot));

}

return 0;

}

poj2104

maksyuki 发表于 oj 分类，标签: 数据结构-划分树

10 1月 2016

K-th Number

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions 阅读全文 »

超客的水墨烟雨

poj3352

poj2942

zoj2588

poj1043

poj3041

poj1422

poj1466

zoj1654

hdu4417

Super Mario

hdu4251

The Famous ICPC Team Again

poj2104

分类目录

标签云

书签

近期评论

2016年1月
一	二	三	四	五	六	日
« 12月				2月 »
				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