250 Problem Statement
You have two favorite music bands. Each of them has just recorded a new album. You have bought both albums.
You know the durations (in seconds) of songs on each of 阅读全文 »
poj1113
26
1月
2016
Wall
Once upon a time there was a greedy King who ordered his chief Architect to build a wall around the King's castle. The King was so greedy, that he would not listen to his Architect's proposals to build a beautiful brick wall with a perfect shape and nice tall towers. Instead, he ordered to build the wall around the whole castle using the least amount of stone and labor, but demanded that the wall should not come closer to the castle than a certain distance. If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will loose his head. Moreover, he demanded Architect to introduce at once a plan of the wall listing the exact amount of resources that are needed to build the wall.
Your task is to help poor Architect to save his head, by writing a program that will find the minimum possible length of the wall that he could build around the castle to satisfy King's requirements.
The task is somewhat simplified by the fact, that the King's castle has a polygonal shape and is situated on a flat ground. The Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of all castle's vertices in feet.
Input
The first line of the input file contains two integer numbers N and L separated by a space. N (3 <= N <= 1000) is the number of vertices in the King's castle, and L (1 <= L <= 1000) is the minimal number of feet that King allows for the wall to come close to the castle.
Next N lines describe coordinates of castle's vertices in a clockwise order. Each line contains two integer numbers Xi and Yi separated by a space (-10000 <= Xi, Yi <= 10000) that represent the coordinates of ith vertex. All vertices are different and the sides of the castle do not intersect anywhere except for vertices.
Output
Write to the output file the single number that represents the minimal possible length of the wall in feet that could be built around the castle to satisfy King's requirements. You must present the integer number of feet to the King, because the floating numbers are not invented yet. However, you must round the result in such a way, that it is accurate to 8 inches (1 foot is equal to 12 inches), since the King will not tolerate larger error in the estimates.
Sample Input
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200
Sample Output
1628
Hint
结果四舍五入就可以了
Source
题目类型：求凸包
算法分析：城堡的围墙长度等于城堡凸包的周长再加上半径为L的圆的周长。这是因为国王的城堡是一个凸多边形，非转角处的围墙可以平行于城堡的边，总长度为凸包周长。而每个转角处的围墙长度是其所占弧的周长，城堡转角处的角度之和为2Pi。所以所有转角处的弧周长之和为圆的周长
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/26 15:38:22 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 sgn (double val) { if (fabs (val) < EPS) return 0; else if (val < 0) return -1; return 1; } struct Point { double x, y; Point () {} Point (double xx, double yy) : x (xx), y (yy) {} Point operator + (const Point &a) const { return Point (x + a.x, y + a.y); } Point operator - (const Point &a) const { return Point (x - a.x, y - a.y); } double operator ^ (const Point &a) const { return x * a.y - y * a.x; } double operator * (const Point &a) const { return x * a.x + y * a.y; } }; double Dist (Point p1, Point p2) { return sqrt ((p2 - p1) * (p2 - p1)); } Point p[maxn]; int n, L; stack <int> sta; bool polarcmp (Point p1, Point p2) { double tt = (p1 - p[1]) ^ (p2 - p[1]); if (sgn (tt) == 1) return true; else if (sgn (tt) == 0 && sgn (Dist (p1, p[1]) - Dist (p2, p[1])) <= 0) return true; return false; } void Garham () { Point start = p[1]; int start_pos = 1; for (int i = 1; i <= n; i++) if (sgn (p[i].x - start.x) == -1 || (sgn (p[i].x - start.x) == 0 && sgn (p[i].y - start.y) == -1)) start = p[i], start_pos = i; swap (p[start_pos], p[1]); sort (p + 2, p + 1 + n, polarcmp); while (!sta.empty ()) sta.pop (); sta.push (1), sta.push (2); for (int i = 3; i <= n; i++) { while (sta.size () >= 2) { int tt1 = sta.top (); sta.pop (); int tt2 = sta.top (); sta.pop (); if (sgn ((p[tt1] - p[tt2]) ^ (p[i] - p[tt2])) <= 0) sta.push (tt2); else { sta.push (tt2), sta.push (tt1); break; } } sta.push (i); } } int main() { //CFF; //CPPFF; while (scanf ("%d%d", &n, &L) != EOF) { for (int i = 1; i <= n; i++) { double x, y; scanf ("%lf%lf", &x, &y); p[i] = Point (x, y); } Garham (); double res = 2 * PI * L; int per = sta.top (); sta.pop (); int start = per, cur; while (!sta.empty ()) { cur = sta.top (); sta.pop (); res += Dist (p[per], p[cur]); per = cur; } res += Dist (p[start], p[cur]); printf ("%.lf\n", res); } return 0; } |
hdu1392
26
1月
2016
Surround the Trees
Problem Description
There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to 阅读全文 »
poj3304
maksyuki 发表于 oj 分类，标签: 计算几何-点线面\点积\叉积
25
1月
2016
Segments
Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in 阅读全文 »
TopCoder SRM#677(Div2)(2/3)
maksyuki 发表于 比赛 分类，标签: 比赛-topcoder
25
1月
2016
250 Problem Statement
A positive integer is called a prime if it has exactly two distinct positive integer divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, ...
A positive integer is called a palindrome if its base-10 representation reads the same forwards and backwards. Some palindromes: 2, 77, 101, 33333, 12344321.
A positive integer is called a palindromic prime if it is both a palindrome and a prime.
You are given two ints: L and R. Compute and return the number of palindromic primes between L and R, inclusive.
Definition
Class: PalindromePrime
Method: count
Parameters: int, int
Returns: int
Method signature: int count(int L, int R)
(be sure your method is public)
题目类型：暴力枚举
算法分析：直接循环枚举判断即可
|
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 |
// BEGIN CUT HERE // END CUT HERE #line 5 "PalindromePrime.cpp" #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; class PalindromePrime { public: int count(int L, int R) { int res = 0; for (int i = L; i <= R; i++) { if (i == 1) continue; bool is_find = true; for (int j = 2; j * j <= i; j++) if (i % j == 0) { is_find = false; break; } if (is_find) { string s; int tt = i; do { s += (char) (tt % 10 + '0'); tt /= 10; } while (tt); int len = s.size (); bool is_have = true; for (int i = 0; i < len / 2; i++) if (s[i] != s[len-1-i]) { is_have = false; break; } if (is_have) res++; } } return res; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); } private: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } void test_case_0() { int Arg0 = 100; int Arg1 = 150; int Arg2 = 2; verify_case(0, Arg2, count(Arg0, Arg1)); } void test_case_1() { int Arg0 = 1; int Arg1 = 9; int Arg2 = 4; verify_case(1, Arg2, count(Arg0, Arg1)); } void test_case_2() { int Arg0 = 929; int Arg1 = 929; int Arg2 = 1; verify_case(2, Arg2, count(Arg0, Arg1)); } void test_case_3() { int Arg0 = 1; int Arg1 = 1; int Arg2 = 0; verify_case(3, Arg2, count(Arg0, Arg1)); } void test_case_4() { int Arg0 = 1; int Arg1 = 1000; int Arg2 = 20; verify_case(4, Arg2, count(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE int main() { PalindromePrime ___test; ___test.run_test(-1); return 0; } // END CUT HERE |
550 Problem Statement
We have four strings: a, b, c, and d.
A superstring of our four strings is any string S such that each of the four strings occurs somewhere in S as a contiguous substring. Note that some superstrings of our four strings always exist.
For example, the string S = a+b+c+d is obviously a superstring of a, b, c, and d.
Find and return the length of the shortest superstring of a, b, c, and d.
Definition
Class: FourStrings
Method: shortestLength
Parameters: string, string, string, string
Returns: int
Method signature: int shortestLength(string a, string b, string c, string d)
(be sure your method is public)
题目类型：暴力枚举+判断
算法分析：由于一共才有4!种排列，所以可以使用next_permutation函数来生成每个排列，然后先判断当前字符串si是否是res的子串，若是则直接判断下一个字符串si+1。否则枚举res后min(res_len, si_len) ~ 0个子串并和si的前len ~ 0个子串比较。将多出来的部分加到res的尾部。最后统计最小值即可
|
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 |
// BEGIN CUT HERE // END CUT HERE #line 5 "FourStrings.cpp" #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; vector <string> s; int res; void SS () { string ans = s[0]; for (int i = 1; i < 4; i++) { if (ans.find (s[i]) != string :: npos) continue; int len = min (ans.size (), s[i].size ()); while (len >= 0 && ans.substr (ans.size () - len).find (s[i].substr (0, len)) == string :: npos) len--; ans += s[i].substr (len); } res = min (res, (int) ans.size ()); } class FourStrings { public: int shortestLength(string a, string b, string c, string d) { s.clear (); s.push_back (a), s.push_back (b), s.push_back (c), s.push_back (d); sort (s.begin (), s.end ()); res = INF; do { SS (); } while (next_permutation (s.begin (), s.end ())); return res; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); } private: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } void test_case_0() { string Arg0 = "abc"; string Arg1 = "ab"; string Arg2 = "bc"; string Arg3 = "b"; int Arg4 = 3; verify_case(0, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_1() { string Arg0 = "a"; string Arg1 = "bc"; string Arg2 = "def"; string Arg3 = "ghij"; int Arg4 = 10; verify_case(1, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_2() { string Arg0 = "top"; string Arg1 = "coder"; string Arg2 = "opco"; string Arg3 = "pcode"; int Arg4 = 8; verify_case(2, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_3() { string Arg0 = "thereare"; string Arg1 = "arelots"; string Arg2 = "lotsof"; string Arg3 = "ofcases"; int Arg4 = 19; verify_case(3, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_4() { string Arg0 = "aba"; string Arg1 = "b"; string Arg2 = "b"; string Arg3 = "b"; int Arg4 = 3; verify_case(4, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_5() { string Arg0 = "x"; string Arg1 = "x"; string Arg2 = "x"; string Arg3 = "x"; int Arg4 = 1; verify_case(5, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } // END CUT HERE }; // BEGIN CUT HERE int main() { FourStrings ___test; ___test.run_test(-1); return 0; } // END CUT HERE |
poj3592
maksyuki 发表于 oj 分类，标签: DP-树形DP, 图论-有向图强连通分量
25
1月
2016
Instantaneous Transference
It was long ago when we played the game Red Alert. There is a magic function for the game objects which is called instantaneous transfer. When an object uses this magic function, it will be transferred to the specified point immediately, regardless of how far it is.
Now there is a mining area, and you are driving an ore-miner truck. Your mission is to take the maximum ores in the field.
The ore area is a rectangle region which is composed by n × m small squares, some of the squares have numbers of ores, while some do not. The ores can't be regenerated after taken.
The starting position of the ore-miner truck is the northwest corner of the field. It must move to the eastern or southern adjacent square, while it can not move to the northern or western adjacent square. And some squares have magic power that can instantaneously transfer the truck to a certain square specified. However, as the captain of the ore-miner truck, you can decide whether to use this magic power or to stay still. One magic power square will never lose its magic power; you can use the magic power whenever you get there.
Input
The first line of the input is an integer T which indicates the number of test cases.
For each of the test case, the first will be two integers N, M (2 ≤ N, M ≤ 40).
The next N lines will describe the map of the mine field. Each of the N lines will be a string that contains M characters. Each character will be an integer X (0 ≤ X ≤ 9) or a '*' or a '#'. The integer X indicates that square has X units of ores, which your truck could get them all. The '*' indicates this square has a magic power which can transfer truck within an instant. The '#' indicates this square is full of rock and the truck can't move on this square. You can assume that the starting position of the truck will never be a '#' square.
As the map indicates, there are K '*' on the map. Then there follows K lines after the map. The next K lines describe the specified target coordinates for the squares with '*', in the order from north to south then west to east. (the original point is the northwest corner, the coordinate is formatted as north-south, west-east, all from 0 to N - 1,M - 1).
Output
For each test case output the maximum units of ores you can take.
Sample Input
1
2 2
11
1*
0 0
Sample Output
3
Source
South Central China 2008 hosted by NUDT
题目类型：有向图强连通分量+缩点+树形DP
算法分析：每个非”#”点和左边、下边的点之间连一条有向边，若遇到”#”点则不连，当然需要将平面图的坐标重新映射一下。对于每个魔法点”*”，需要额外判断是否能够向其目标点连有向边(目标点非”#”才能连)。易知同一个强连通分量中的点可以双向可达，所以可以缩点，用其中所有点的val值的和来表示缩点后的点的点权，缩点后的图是一个有向无环图且没有重边，所以可以看做是树。使用dp[i]表示以i为根的子树所具有的最大价值。dp[i]初始化成对应缩点后的点权。状态转移方程为dp[u] = max (dp[u], vval[u] + dp[v])，vval[u]表示u点处的点权(缩点后)且v是u的子节点。最后输出顶点1所在缩点处的dp值即可
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/25 14:26:33 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 * 66 + 66; int dfn[maxn], low[maxn], belong[maxn], val[maxn], vval[maxn], dp[maxn]; int n, m, id, tot; char g[maxn][maxn]; bool instack[maxn]; vector <int> gg[maxn], ggg[maxn]; vector <PII> in; stack <int> sta; const int dx[] = {0, 1}; const int dy[] = {1, 0}; void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < gg[u].size (); i++) { int v = gg[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; vval[tot] += val[tt]; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (vval, 0, sizeof (vval)); memset (instack, false, sizeof (instack)); id = tot = 0; while (!sta.empty ()) sta.pop (); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } void dp_dfs (int u) { for (int i = 0; i < ggg[u].size (); i++) { int v = ggg[u][i]; dp_dfs (v); dp[u] = max (dp[u], vval[u] + dp[v]); } } int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { scanf ("%d%d", &n, &m); int k = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { scanf (" %c", &g[i][j]); if (g[i][j] == '*') k++; } in.clear (); for (int i = 1; i <= k; i++) { int x, y; scanf ("%d%d", &x, &y); x++, y++; in.push_back (PII (x, y)); } for (int i = 0; i < maxn; i++) gg[i].clear (); k = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (g[i][j] == '#') { val[(i-1)*m+j] = 0; continue; } for (int q = 0; q < 2; q++) { int xx = i + dx[q], yy = j + dy[q]; if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] != '#') gg[(i-1)*m+j].push_back ((xx - 1) * m + yy); } if (g[i][j] >= '0' && g[i][j] <= '9') val[(i-1)*m+j] = g[i][j] - '0'; else val[(i-1)*m+j] = 0; if (g[i][j] == '*') { int xx = in[k].first, yy = in[k].second; k++; if (g[xx][yy] != '#') gg[(i-1)*m+j].push_back ((xx - 1) * m + yy); } } n = m * n;//important!!! SS (); for (int i = 0; i < maxn; i++) ggg[i].clear (); for (int u = 1; u <= n; u++) for (int i = 0; i < gg[u].size (); i++) { int v = gg[u][i]; if (belong[u] != belong[v]) ggg[belong[u]].push_back (belong[v]); } for (int i = 1; i <= tot; i++) dp[i] = vval[i]; dp_dfs (belong[1]); printf ("%d\n", dp[belong[1]]); } return 0; } |
poj1904
maksyuki 发表于 oj 分类，标签: 图论-二分图完备匹配, 图论-有向图强连通分量
25
1月
2016
King's Quest
Once upon a time there lived a king and he had N sons. And there were N beautiful girls in the kingdom and the king knew about each of his sons which of those girls he did like. The sons of the king were young and light-headed, so it was possible for one son to like several girls.
So the king asked his wizard to find for each of his sons the girl he liked, so that he could marry her. And the king's wizard did it -- for each son the girl that he could marry was chosen, so that he liked this girl and, of course, each beautiful girl had to marry only one of the king's sons.
However, the king looked at the list and said: "I like the list you have made, but I am not completely satisfied. For each son I would like to know all the girls that he can marry. Of course, after he marries any of those girls, for each other son you must still be able to choose the girl he likes to marry."
The problem the king wanted the wizard to solve had become too hard for him. You must save wizard's head by solving this problem.
Input
The first line of the input contains N -- the number of king's sons (1 <= N <= 2000). Next N lines for each of king's sons contain the list of the girls he likes: first Ki -- the number of those girls, and then Ki different integer numbers, ranging from 1 to N denoting the girls. The sum of all Ki does not exceed 200000.
The last line of the case contains the original list the wizard had made -- N different integer numbers: for each son the number of the girl he would marry in compliance with this list. It is guaranteed that the list is correct, that is, each son likes the girl he must marry according to this list.
Output
Output N lines.For each king's son first print Li -- the number of different girls he likes and can marry so that after his marriage it is possible to marry each of the other king's sons. After that print Li different integer numbers denoting those girls, in ascending order.
Sample Input
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
Sample Output
2 1 2
2 1 2
1 3
1 4
Hint
This problem has huge input and output data,use scanf() and printf() instead of cin and cout to read data to avoid time limit exceed.
Source
题目类型：有向图强连通分量(二分图完备匹配)
算法分析：这道题直观上是一道求解二分图完备匹配并输出所有满足条件的问题。但是由于顶点数和边数比较多，所以直接使用找增广链的算法会超时。这里利用二分图完备匹配的性质来简化问题。如何才能不通过寻找增广链而直接确定是否存在增广链呢？让我们再次回到初始的想法，如果给定的完备匹配中xi -> yi，现在我们想让xi指向yj。如果让xi -> yj的话，那么yi显然对于xi已经没用了，又因为最终的匹配必然是一个完备匹配，即yi一定会被某一个xk(1 <= k <= n)所匹配。所以假如寻找到了增广链，那么增广链的最后一条边所指向的顶点必然是yi。假如我们由yi向xi再连一条边会发生什么呢？ 很明显，形成了一个环！也就是说，形成了一个强连通分量。所以说，如果xi可以选择yj(即xi喜欢yi且可以结婚)，那么xi和yj必然属于同一个强连通分量。所以此题可用强连通分量来求解，求解出强连通分量后直接统计即可
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/25 12:38:12 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 = 2 * 2000 + 66; int dfn[maxn], low[maxn], belong[maxn]; int n, id, tot; bool instack[maxn], gg[maxn][maxn]; vector <int> g[maxn]; stack <int> sta; void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (instack, false, sizeof (instack)); id = tot = 0; while (!sta.empty ()) sta.pop (); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { for (int i = 0; i < maxn; i++) g[i].clear (); memset (gg, false, sizeof (gg)); for (int i = 1; i <= n; i++) { int num; scanf ("%d", &num); for (int j = 1; j <= num; j++) { int u; scanf ("%d", &u); g[i].push_back (n + u); gg[i][u] = true; } } for (int i = 1; i <= n; i++) { int u; scanf ("%d", &u); g[n+u].push_back (i); } SS (); vector <int> temp; for (int i = 1; i <= n; i++) { temp.clear (); for (int j = n + 1; j <= 2 * n; j++) if (gg[i][j-n] && belong[i] == belong[j]) temp.push_back (j - n); sort (temp.begin (), temp.end ()); printf ("%d", temp.size ()); for (int j = 0; j < temp.size (); j++) printf (" %d", temp[j]); puts (""); } } return 0; } |
poj3160
maksyuki 发表于 oj 分类，标签: DP-线性DP, 图论-有向图强连通分量
24
1月
2016
Father Christmas flymouse
After retirement as contestant from WHU ACM Team, flymouse volunteered to do the odds and ends such as cleaning out the computer lab for training as extension of his contribution to the team. When Christmas came, flymouse played Father Christmas to give gifts to the team members. The team members lived in distinct rooms in different buildings on the campus. To save vigor, flymouse decided to choose only one of those rooms as the place to start his journey and follow directed paths to visit one room after another and give out gifts en passant until he could reach no more unvisited rooms.
During the days on the team, flymouse left different impressions on his teammates at the time. Some of them, like LiZhiXu, with whom flymouse shared a lot of candies, would surely sing flymouse’s deeds of generosity, while the others, like snoopy, would never let flymouse off for his idleness. flymouse was able to use some kind of comfort index to quantitize whether better or worse he would feel after hearing the words from the gift recipients (positive for better and negative for worse). When arriving at a room, he chould choose to enter and give out a gift and hear the words from the recipient, or bypass the room in silence. He could arrive at a room more than once but never enter it a second time. He wanted to maximize the the sum of comfort indices accumulated along his journey.
Input
The input contains several test cases. Each test cases start with two integers N and M not exceeding 30 000 and 150 000 respectively on the first line, meaning that there were N team members living in N distinct rooms and M direct paths. On the next N lines there are N integers, one on each line, the i-th of which gives the comfort index of the words of the team member in the i-th room. Then follow M lines, each containing two integers i and j indicating a directed path from the i-th room to the j-th one. Process to end of file.
Output
For each test case, output one line with only the maximized sum of accumulated comfort indices.
Sample Input
2 2
14
21
0 1
1 0
Sample Output
35
Hint
32-bit signed integer type is capable of doing all arithmetic.
Source
POJ Monthly--2006.12.31, Sempr
题目类型：有向图强连通分量+缩点+DP
算法分析：易知在同一个强连通分量中的点的权值等于所有正值点的点权之和。缩点后，在构建出来的图上DP，dp[i]表示i点处的最大值，初始化为缩点后该点的点权。状态转移方程为dp[i] = max (dp[i], max (vval[i] + dp[j])), j至i有一条有向边，vval[i]为i点处的点权。最后使用拓扑序转移计算即可，注意若点权为负值，由于可以不进去，所以缩点后点权可以赋值为0！！！dp[i]要使用long long！！！
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/24 18:56:38 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 = 30000 + 66; int dfn[maxn], low[maxn], belong[maxn], val[maxn], vval[maxn], indeg[maxn]; LL dp[maxn]; int n, m, id, tot; bool instack[maxn]; vector <int> g[maxn], gg[maxn]; stack <int> sta; void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; if (val[tt] > 0) vval[tot] += val[tt]; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (instack, false, sizeof (instack)); memset (vval, 0, sizeof (vval)); tot = id = 0; while (!sta.empty ()) sta.pop (); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } int main() { //CFF; //CPPFF; while (scanf ("%d%d", &n, &m) != EOF) { for (int i = 1; i <= n; i++) scanf ("%d", &val[i]); for (int i = 0; i < maxn; i++) g[i].clear (); for (int i = 1; i <= m; i++) { int u, v; scanf ("%d%d", &u, &v); u++, v++; g[u].push_back (v); } SS (); memset (indeg, 0, sizeof (indeg)); for (int i = 0; i < maxn; i++) gg[i].clear (); for (int u = 1; u <= n; u++) for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (belong[u] != belong[v]) { indeg[belong[v]]++; gg[belong[u]].push_back (belong[v]); } } queue <int> qu; for (int i = 1; i <= tot; i++) { if (!indeg[i]) qu.push (i); dp[i] = vval[i]; } while (!qu.empty ()) { int tt = qu.front (); qu.pop (); for (int i = 0; i < gg[tt].size (); i++) { int v = gg[tt][i]; indeg[v]--; dp[v] = max (dp[v], vval[v] + dp[tt]); if (!indeg[v]) qu.push (v); } } LL res = -INF; for (int i = 1; i <= tot; i++) res = max (res, dp[i]); printf ("%lld\n", res); } return 0; } |
poj1269
maksyuki 发表于 oj 分类，标签: 计算几何-点线面\点积\叉积
24
1月
2016
Intersecting Lines
We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect.
Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000.
Input
The first line contains an integer N between 1 and 10 describing how many pairs of lines are represented. The next N lines will each contain eight integers. These integers represent the coordinates of four points on the plane in the order x1y1x2y2x3y3x4y4. Thus each of these input lines represents two lines on the plane: the line through (x1,y1) and (x2,y2) and the line through (x3,y3) and (x4,y4). The point (x1,y1) is always distinct from (x2,y2). Likewise with (x3,y3) and (x4,y4).
Output
There should be N+2 lines of output. The first line of output should read INTERSECTING LINES OUTPUT. There will then be one line of output for each pair of planar lines represented by a line of input, describing how the lines intersect: none, line, or point. If the intersection is a point then your program should output the x and y coordinates of the point, correct to two decimal places. The final line of output should read "END OF OUTPUT".
Sample Input
5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5
Sample Output
INTERSECTING LINES OUTPUT
POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
END OF OUTPUT
Source
题目类型：直线相交
算法分析：对于每对直线，依次使用叉积判断是否是重合还是相交，然后再判断其中一条线矢量端点是否在另一条直线矢量端点为对角线的矩形内。若判断为相交，则使用矢量计算出交点
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/24 14:50:18 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 sgn (double val) { if (fabs (val) < EPS) return 0; else if (val < 0) return -1; return 1; } struct Point { double x, y; Point () {} Point (double xx, double yy) : x (xx), y (yy) {} Point operator - (const Point &a) const { return Point (x - a.x, y - a.y); } double operator ^ (const Point &a) const { return x * a.y - y * a.x; } double operator * (const Point &a) const { return x * a.x + y * a.y; } }; struct Line { Point s, e; Line () {} Line (Point ss, Point ee) : s (ss), e (ee) {} pair <int, Point> operator & (const Line &a) const { Point res = s; if (sgn ((s - e) ^ (a.s - a.e)) == 0) { if (sgn ((s - a.e) ^ (a.s - a.e)) == 0) return make_pair (0, res); else return make_pair (1, res); } double t = ((s - a.s) ^ (a.s - a.e)) / ((s - e) ^ (a.s - a.e)); res.x += (e.x - s.x) * t; res.y += (e.y - s.y) * t; return make_pair (2, res); } }; int main() { //CFF; //CPPFF; int n; while (scanf ("%d", &n) != EOF) { double x1, y1, x2, y2, x3, y3, x4, y4; puts ("INTERSECTING LINES OUTPUT"); for (int i = 1; i <= n; i++) { scanf ("%lf%lf%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4); Line l1 (Point (x1, y1), Point (x2, y2)); Line l2 (Point (x3, y3), Point (x4, y4)); pair <int, Point> tt = l1 & l2; if (tt.first == 0) puts ("LINE"); else if (tt.first == 1) puts ("NONE"); else printf ("POINT %.2lf %.2lf\n", tt.second.x, tt.second.y); } puts ("END OF OUTPUT"); } return 0; } |
poj2398
maksyuki 发表于 oj 分类，标签: 计算几何-点线面\点积\叉积
24
1月
2016
Toy Storage
Mom and dad have a problem: their child, Reza, never puts his toys away when he is finished playing with them. They gave Reza a rectangular box to put his toys in. Unfortunately, Reza is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for Reza to find his favorite toys anymore.
Reza's parents came up with the following idea. They put cardboard partitions into the box. Even if Reza keeps throwing his toys into the box, at least toys that get thrown into different partitions stay separate. The box looks like this from the top:
We want for each positive integer t, such that there exists a partition with t toys, determine how many partitions have t, toys.
Input
The input consists of a number of cases. The first line consists of six integers n, m, x1, y1, x2, y2. The number of cardboards to form the partitions is n (0 < n <= 1000) and the number of toys is given in m (0 < m <= 1000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1, y1) and (x2, y2), respectively. The following n lines each consists of two integers Ui Li, indicating that the ends of the ith cardboard is at the coordinates (Ui, y1) and (Li, y2). You may assume that the cardboards do not intersect with each other. The next m lines each consists of two integers Xi Yi specifying where the ith toy has landed in the box. You may assume that no toy will land on a cardboard.
A line consisting of a single 0 terminates the input.
Output
For each box, first provide a header stating "Box" on a line of its own. After that, there will be one line of output per count (t > 0) of toys in a partition. The value t will be followed by a colon and a space, followed the number of partitions containing t toys. Output will be sorted in ascending order of t for each box.
Sample Input
4 10 0 10 100 0
20 20
80 80
60 60
40 40
5 10
15 10
95 10
25 10
65 10
75 10
35 10
45 10
55 10
85 10
5 6 0 10 60 0
4 3
15 30
3 1
6 8
10 10
2 1
2 8
1 5
5 5
40 10
7 9
0
Sample Output
Box
2: 5
Box
1: 4
2: 1
Source
题目类型：叉积+二分枚举
算法分析：使用叉积来判断点在一条直线的左右侧，可以二分枚举直线来判断。注意在枚举前要先将直线按照从左至右的顺序排好序！！！
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/24 14:00: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 = 1000 + 66; struct Point { double x, y; Point () {} Point (double xx, double yy) : x (xx), y (yy) {} Point operator - (const Point &a) const { return Point (x - a.x, y - a.y); } double operator ^ (const Point &a) const { return x * a.y - y * a.x; } double operator * (const Point &a) const { return x * a.x + y * a.y; } }; struct Line { Point s, e; Line () {} Line (Point ss, Point ee) : s (ss), e (ee) {} }; Line line[maxn]; int res[maxn], cnt[maxn], n, m; double xmult (Point p1, Point p2, Point p3) { return (p2 - p1) ^ (p3 - p1); } int sgn (double val) { if (fabs (val) < EPS) return 0; else if (val < 0) return -1; return 1; } bool cmp (Line a, Line b) { return a.s.x < b.s.x; } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { if (n == 0) break; scanf ("%d", &m); double x1, y1, x2, y2; scanf ("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); for (int i = 1; i <= n; i++) { double Ui, Li; scanf ("%lf%lf", &Ui, &Li); line[i] = Line (Point (Ui, y1), Point (Li, y2)); } sort (line + 1, line + 1 + n, cmp); memset (res, 0, sizeof (res)); memset (cnt, 0, sizeof (cnt)); for (int i = 1; i <= m; i++) { double x, y; scanf ("%lf%lf", &x, &y); int low = 1, high = n; while (low <= high) { int mid = (low + high) >> 1; double tt = xmult (line[mid].s, Point (x, y), line[mid].e); if (sgn (tt) == 1) high = mid - 1; else low = mid + 1; } res[max(low,high)]++; } puts ("Box"); int maxval = -INF; for (int i = 1; i <= n + 1; i++) { cnt[res[i]]++; if (res[i]) maxval = max (maxval, res[i]); } for (int i = 1; i <= maxval; i++) if (cnt[i]) printf ("%d: %d\n", i, cnt[i]); } return 0; } |
poj2318
maksyuki 发表于 oj 分类，标签: 计算几何-点线面\点积\叉积
24
1月
2016
TOYS
Calculate the number of toys that land in each bin of a partitioned toy box.Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.
John's parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.
For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.
Input
The input file contains one or more problems. The first line of a problem consists of six integers, n m x1 y1 x2 y2. The number of cardboard partitions is n (0 < n <= 5000) and the number of toys is m (0 < m <= 5000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1,y1) and (x2,y2), respectively. The following n lines contain two integers per line, Ui Li, indicating that the ends of the i-th cardboard partition is at the coordinates (Ui,y1) and (Li,y2). You may assume that the cardboard partitions do not intersect each other and that they are specified in sorted order from left to right. The next m lines contain two integers per line, Xj Yj specifying where the j-th toy has landed in the box. The order of the toy locations is random. You may assume that no toy will land exactly on a cardboard partition or outside the boundary of the box. The input is terminated by a line consisting of a single 0.
Output
The output for each problem will be one line for each separate bin in the toy box. For each bin, print its bin number, followed by a colon and one space, followed by the number of toys thrown into that bin. Bins are numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate the output of different problems by a single blank line.
Sample Input
5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0
Sample Output
0: 2
1: 1
2: 1
3: 1
4: 0
5: 1
0: 2
1: 2
2: 2
3: 2
4: 2
Hint
As the example illustrates, toys that fall on the boundary of the box are "in" the box.
Source
题目类型：叉乘+二分枚举
算法分析：使用叉乘可以判断点在一个线段的左侧还是右侧。然后二分枚举直线并判断即可
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/24 10:51:12 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 * 2 + 66; int n, m; int sgn (double a) { if (fabs (a) < EPS) return 0; else if (a < 0) return -1; else return 1; } struct Point { double x, y; Point () {} Point (double xx, double yy) : x (xx), y (yy) {} Point operator + (const Point &a) const { return Point (x + a.x, y + a.y); } Point operator - (const Point &a) const { return Point (x - a.x, y - a.y); } double operator ^ (const Point &a) const { return x * a.y - y * a.x; } double operator * (const Point &a) const { return x * a.x + y * a.y; } }; struct Line { Point s, e; Line () {} Line (Point ss, Point ee) : s (ss), e (ee) {} }; Line line[maxn]; int res[maxn]; double xmul (Point p1, Point p2, Point p3) { return (p2 - p1) ^ (p3 - p1); } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { if (n == 0) break; scanf ("%d", &m); double x1, y1, x2, y2; scanf ("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); for (int i = 1; i <= n; i++) { double Ui, Li; scanf ("%lf%lf", &Ui, &Li); line[i] = Line (Point (Ui, y1), Point (Li, y2)); } memset (res, 0, sizeof (res)); for (int i = 1; i <= m; i++) { double x, y; scanf ("%lf%lf", &x, &y); int low = 1, high = n; while (low <= high) { int mid = (low + high) >> 1; double tt = xmul (line[mid].s, Point (x, y), line[mid].e); if (sgn (tt) == 1) high = mid - 1; if (sgn (tt) == -1) low = mid + 1; } res[min(low,high)]++; } for (int i = 0; i <= n; i++) printf ("%d: %d\n", i, res[i]); puts (""); } return 0; } |
poj1236
maksyuki 发表于 oj 分类，标签: 图论-有向图强连通分量
23
1月
2016
Network of Schools
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.
Input
The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.
Output
Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.
Sample Input
5
2 4 3 0
4 5 0
0
0
1 0
Sample Output
12
Source
题目类型：有向图强连通分量+缩点
算法分析：易知同一个强连通分量A中的学校之间可以相互拷贝软件，若外部一个点a和A中的点b相连，则a处的软件可以传遍A。反之若A中的点a和外部的一个点b相连，则b和A中所有的点相连，所以可以缩点。最后答案a的结果是缩点后出度为0的顶点个数。之后为了能够将缩点后的图填最少的边构建成一个强连通图，易知需要在出度为0的点和入度为0的点之间连边。直到所有出度为0的点和入度为0的点都没有为止。这样答案b的结果就是出度为0的点个数和入度为0的点个数之间的较大值。注意：当缩点后只有一个点时，需要特判输出0！！！
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/23 14:04:32 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 = 166 + 66; int dfn[maxn], low[maxn], belong[maxn], indeg[maxn], outdeg[maxn]; int n, id, tot; bool instack[maxn]; vector <int> g[maxn]; stack <int> sta; void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (instack, false, sizeof (instack)); id = tot = 0; while (!sta.empty ()) sta.pop (); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } 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 u; while (scanf ("%d", &u) != EOF) { if (u == 0) break; g[i].push_back (u); } } SS (); set <PII> seta; memset (indeg, 0, sizeof (indeg)); memset (outdeg, 0, sizeof (outdeg)); for (int u = 1; u <= n; u++) for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (belong[u] != belong[v] && seta.find (PII (belong[u], belong[v])) == seta.end ()) { indeg[belong[v]]++; outdeg[belong[u]]++; seta.insert (PII (belong[u], belong[v])); } } int resa = 0, resb = 0; for (int i = 1; i <= tot; i++) { if (!indeg[i]) resa++; if (!outdeg[i]) resb++; } printf ("%d\n", resa); if (tot == 1) puts ("0"); else printf ("%d\n", max (resa, resb)); } return 0; } |
poj2553
maksyuki 发表于 oj 分类，标签: 图论-有向图强连通分量
23
1月
2016
The Bottom of a Graph
We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges. Then G=(V,E) is called a directed graph.
Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1). Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→vn+1).
Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e., bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.
Input
The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=(V,E), where the vertices will be identified by the integer numbers in the set V={1,...,v}. You may assume that 1<=v<=5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,...,ve,we with the meaning that (vi,wi)∈E. There are no edges other than specified by these pairs. The last test case is followed by a zero.
Output
For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.
Sample Input
3 3
1 3 2 3 3 1
2 1
1 2
0
Sample Output
1 3
2
Source
题目类型：有向图强连通分量(Tarjan)+缩点
算法分析：本题要找所有满足”能够到达其他顶点w(w != u)的点u是否能够从w点到达”的所有的u点，即不考察那些u不可达的点的情况。由于同一个强连通分量中的顶点都是双向可达的，所以其中任意一个点对于同一个强连通分量中的其它点都是满足条件的，可以缩点。易知缩点后得到的图中出度为0的缩点都满足条件
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/23 13:13:31 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 + 66; int dfn[maxn], low[maxn], belong[maxn], outdeg[maxn]; bool instack[maxn]; int n, m, id, tot; vector <int> g[maxn], num[maxn], out; stack <int> sta; void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; num[tot].push_back (tt); } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (instack, false, sizeof (instack)); id = tot = 0; while (!sta.empty ()) sta.pop (); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { if (n == 0) break; scanf ("%d", &m); for (int i = 0; i < maxn; i++) g[i].clear (), num[i].clear (); for (int i = 1; i <= m; i++) { int u, v; scanf ("%d%d", &u, &v); g[u].push_back (v); } SS (); memset (outdeg, 0, sizeof (outdeg)); for (int u = 1; u <= n; u++) for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (belong[u] != belong[v]) outdeg[belong[u]]++; } out.clear (); for (int i = 1; i <= tot; i++) if (!outdeg[i]) { for (int j = 0; j < num[i].size (); j++) out.push_back (num[i][j]); } sort (out.begin (), out.end ()); for (int i = 0; i < out.size (); i++) { if (i == 0) printf ("%d", out[i]); else printf (" %d", out[i]); } puts (""); } return 0; } |
poj2186
maksyuki 发表于 oj 分类，标签: 图论-有向图强连通分量
22
1月
2016
Popular Cows
Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.
Input
* Line 1: Two space-separated integers, N and M
* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.
Output
* Line 1: A single integer that is the number of cows who are considered popular by every other cow.
Sample Input
3 3
1 2
2 1
2 3
Sample Output
1
Hint
Cow 3 is the only cow of high popularity.
Source
题目类型：有向图重连通分量(Tarjan)+缩点
算法分析：由于仰慕关系可以传递，则若一个强连通分量Q中的某个点被外部点A所仰慕，则Q中所有点都会被A仰慕。同样，若Q中的某个点仰慕某个外部点B，则Q中所有点都会仰慕B。所以可以缩点，找新构成的图中出度为0的点(注意这个点是可能是缩点！！！)，若出度为0的点的个数不为1，则输出0。否则输出当前缩点中点的个数
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/22 21:06:14 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 dfn[maxn], low[maxn], belong[maxn], outdeg[maxn], num[maxn]; int n, m, id, tot; bool instack[maxn]; vector <int> g[maxn]; stack <int> sta; void dfs (int u) { dfn[u] = low[u] = ++id; instack[u] = true; sta.push (u); for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; num[tot]++; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (num, 0, sizeof (num)); memset (instack, false, sizeof (instack)); tot = id = 0; while (!sta.empty ()) sta.pop (); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } int main() { //CFF; //CPPFF; while (scanf ("%d%d", &n, &m) != EOF) { for (int i = 0; i < maxn; i++) g[i].clear (); for (int i = 1; i <= m; i++) { int u, v; scanf ("%d%d", &u, &v); g[u].push_back (v); } SS (); memset (outdeg, 0, sizeof (outdeg)); for (int u = 1; u <= n; u++) for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (belong[u] != belong[v]) outdeg[belong[u]]++; } int res = 0, pos = 1; for (int i = 1; i <= tot; i++) if (!outdeg[i]) pos = i, res++; if (res == 1) printf ("%d\n", num[pos]); else puts ("0"); } return 0; } |
poj2762
maksyuki 发表于 oj 分类，标签: 图论-拓扑排序, 图论-有向图强连通分量
22
1月
2016
Going from u to v or from v to u?
In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?
Input
The first line contains a single integer T, the number of test cases. And followed T cases.
The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.
Output
The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.
Sample Input
1
3 3
1 2
2 3
3 1
Sample Output
Yes
Source
POJ Monthly--2006.02.26,zgl & twb
题目类型：有向图强连通分量(Tarjan) +缩点+拓扑排序判定
算法分析：这个题目要判断一个图是否是单连通的，由于图中同一个强连通分量中的点一定是单连通的，所以可以不用考虑同一个强连通分量中的所有点之间的连通情况继而将其缩成一个点。然后考察缩完点之后的图，易知这个图任意两点之间最多单向可达。由于处理后得到的图仍然是有向图，所以可以对图进行拓扑排序。对于得到的拓扑序列，相邻的节点要么是”非同层”顶点，要么是”同层”顶点(拓扑排序过程中某次入度为0的顶点之间互为”同层”顶点)。对于以上两种情况，只要满足拓扑序中所有相邻的顶点之间邻接，则由传递性可知，每个顶点之间都可达
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/22 19:11:57 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 dfn[maxn], low[maxn], belong[maxn]; bool instack[maxn]; stack <int> sta; vector <int> g[maxn]; int n, m, id, tot; int gg[maxn][maxn], indeg[maxn], topo[maxn]; void Init () { for (int i = 0; i < maxn; i++) g[i].clear (); } void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (instack, false, sizeof (instack)); while (!sta.empty ()) sta.pop (); tot = id = 0; for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { Init (); scanf ("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf ("%d%d", &u, &v); g[u].push_back (v); } SS (); memset (gg, 0, sizeof (gg)); memset (indeg, 0, sizeof (indeg)); for (int u = 1; u <= n; u++) for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (belong[u] != belong[v]) { gg[belong[u]][belong[v]] = 1; indeg[belong[v]]++; } } queue <int> qua; for (int i = 1; i <= tot; i++) if (!indeg[i]) qua.push (i); int len = 0; while (!qua.empty ()) { int u = qua.front (); qua.pop (); topo[++len] = u; for (int v = 1; v <= tot; v++) if (u != v && gg[u][v]) { indeg[v]--; if (!indeg[v]) qua.push (v); } } bool is_valid = true; for (int i = 1; i <= tot - 1; i++) if (!gg[topo[i]][topo[i+1]]) { is_valid = false; break; } if (is_valid) puts ("Yes"); else puts ("No"); } return 0; } |
poj3177
maksyuki 发表于 oj 分类，标签: 图论-求解割点\割边(Tarjan)
22
1月
2016
Redundant Paths
In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another.
Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way.
There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.
Input
Line 1: Two space-separated integers: F and R
Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.
Output
Line 1: A single integer that is the number of new paths that must be built.
Sample Input
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
Sample Output
2
Hint
Explanation of the sample:
One visualization of the paths is:
1 2 3
+---+---+
| |
| |
6 +---+---+ 4
/ 5
/
/
7 +
Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions.
1 2 3
+---+---+
: | |
: | |
6 +---+---+ 4
/ 5 :
/ :
/ :
7 + - - - -
Check some of the routes:
1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2
1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4
3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7
Every pair of fields is, in fact, connected by two routes.
It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.
Source
题目类型：无向图求割边(Tarjan)+缩点
算法分析：这里虽然存在重边，但是可以不将重边加入到图中，然后使用low值将边重连通分量进行划分，若图中没有重边，则low值相同的顶点一定在一个边重连通分量中(因为有环)。所以此时可以双重循环枚举找邻接顶点，若两个顶点的low不同，则它们各自所在的“缩点”的度数自加1
|
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 |
/************************************************* 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], deg[maxn]; int n, m, id; vector <int> g[maxn]; set <PII> seta; void Init (int rt) { 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; } void dfs (int u, int par) { for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!vis[v]) { vis[v] = 1; dfn[v] = low[v] = ++id; dfs (v, u); low[u] = min (low[u], low[v]); } else if (v != par) low[u] = min (low[u], dfn[v]); } } void SS () { for (int u = 1; u <= n; u++) for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (low[u] != low[v]) deg[low[u]]++; } } 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); if (seta.find (PII (u, v)) != seta.end ()) continue; seta.insert (PII (u, v)), seta.insert (PII (v, u)); g[u].push_back (v); g[v].push_back (u); } dfs (1, -1); SS (); int res = 0; for (int i = 1; i <= n; i++) if (deg[i] == 1) res++; printf ("%d\n", (res + 1) / 2); } return 0; } |