Created
October 19, 2014 11:59
-
-
Save stattrak-dragonlore/d67b3696048b33e49739 to your computer and use it in GitHub Desktop.
cpp template for programming contest
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <sstream> <numeric> <functional> | |
| hash_map: | |
| vc2005: | |
| using namespace stdext; | |
| #include <hash_map> | |
| gcc: | |
| #include <ext/hash_map> | |
| using namespace __gnu_cxx; | |
| struct str_hash | |
| { | |
| size_t operator() (const string& str) const | |
| { | |
| return __stl_hash_string(str.c_str()); | |
| } | |
| }; | |
| hash_map<string, int, str_hash> hmap; | |
| struct eqstr | |
| { | |
| bool operator() (const char* str1, const char* str2) const | |
| { | |
| return strcmp(str1, str2)==0; | |
| } | |
| }; | |
| hash_map<const char*, int, hash(const char*), eqstr> hmap; | |
| typedef pair<int,int> ii; | |
| //#define DEBUG | |
| freopen("d:\\input.txt","r",stdin); | |
| notes: | |
| 读一行到字符buf： char str1[20]; gets(str1); 可以有空格，可以是空行，遇到回车结束 | |
| 输入double: scanf("%lf", &d) | |
| 将一个字符串parse到一个数组： | |
| 比如一个char buf[] ="83.5 64.1 5.2 72.62 "; | |
| 假如里面数的个数不一定.. | |
| 通过sscanf将其读到一个float数组F.. | |
| cur = buf; | |
| while(sscanf(cur, "%f %n", &F[i++], &len)!=EOF) cur+=len; | |
| 其中t存储到每一次输入的charater数(%n) | |
| while(getline(P, p, ',')) // 将流P输入到string p中, 直到遇到逗号','结束 | |
| int str2num(string s) | |
| { int num; | |
| istringstream ss(s); | |
| ss>>num; return num; | |
| } | |
| string num2str(double i) | |
| { | |
| stringstream ss; | |
| ss<<i; | |
| return ss.str(); | |
| } | |
| // 筛法求素数 | |
| #define N 10000 | |
| bool notPrime[N+1]; | |
| int primes[N]; | |
| int primesCounter=0; /* the number of primes */ | |
| /* | |
| Time Complexity: O(N) | |
| 每个合数必有一个最小素因子。 | |
| 每个合数仅被它的最小素因子筛掉 | |
| */ | |
| void sieve() | |
| { | |
| memset(notPrime, 0, sizeof(prime)); | |
| for (int i = 2; i <= N; i++) | |
| { | |
| if (!notPrime[i]) /* is prime */ | |
| primes [ primesCounter ++ ]= i; | |
| for (int j = 0; j < primesCounter && i * primes[j] <= N; j++) | |
| { | |
| /* 当 i 不含有因子 primes[j]或者刚好含有因子primes[j]时, | |
| * primes[j]一定是 i*primes[j] 的最小因子 */ | |
| notPrime[i * primes[j]] = true; | |
| /* 当 i 含有因子 primes[j]时.*/ | |
| if (i % primes[j] == 0) break; | |
| /* i*primes[j+1], i*primes[j+2].. | |
| * 这些合数肯定被primes[j]*乘以某个数筛掉. */ | |
| } | |
| } | |
| } | |
| // printf("primes Counter = %d\n", cnt); | |
| vector <pair <int, int> > primeFactor(int n) | |
| { | |
| vector < pair <int, int> > v; | |
| for(int i=0; i<primesCounter && primes[i] * primes[i] <= n; i++ ) { | |
| int k = 0 ; | |
| while ( n %primes[i] == 0 ) { | |
| k ++ ; | |
| n/=primes[i] ; | |
| } | |
| if ( k ) | |
| v.push_back(make_pair( primes[i], k)); | |
| } | |
| if (n != 1) | |
| v.push_back (pair <int, int> (n, 1)); | |
| return v; | |
| } | |
| long long catalan(long long n) // MAX n=33 | |
| { | |
| if(n==0) return 1; | |
| else return (4*n-2)*catalan(n-1)/(n+1); | |
| } | |
| // 求n的约数 return vector<int> | |
| // uses primeFactor(n) | |
| vector<int> factor(int n) | |
| { | |
| vector<pair<int, int> > v = primeFactor(n); // 分解成素数的积 | |
| vector<int> factor; //存放约数 | |
| int sz=v.size(); | |
| int bound=1; | |
| for(int j=0; j<sz; j++) // 加1法枚举约数 | |
| bound*=(v[j].second+1); // 求出最大值bound.. | |
| for(int j=0; j<bound; j++) { // 0 ~ bound-1 | |
| int fac= 1; | |
| int q=j; | |
| for(int k=0; q && k<sz; k++) { // 模出每一位取几个 | |
| int tt=q % (v[k].second+1); | |
| for(int a=0; a< tt; a++) | |
| fac*=v[k].first; | |
| q/=(v[k].second+1); | |
| } | |
| factor.push_back(fac); | |
| } | |
| return factor; | |
| } | |
| int PHI (int n) // 欧拉函数 | |
| { | |
| if (n == 1) | |
| return 1; | |
| int m = n; | |
| for(int i=0; i< cnt && primes[i]*primes[i] <= m; i++){ // cnt is prime counter | |
| if (m % primes[i] == 0) { | |
| n -= (n / primes[i]); | |
| do { | |
| m /= primes[i]; | |
| } while (m % primes[i] == 0); | |
| } | |
| } | |
| if (m != 1) | |
| n -= (n / m); | |
| return n; | |
| } | |
| /***********************************/ | |
| //最大公约数 a, b不全为0 | |
| int gcd(int a, int b) | |
| { | |
| if (a==0) | |
| return b; | |
| else return (b, a%b); | |
| } | |
| // 三元组 | |
| template <typename T> | |
| class ternary { | |
| public: | |
| ternary(T a, T b, T c) | |
| { | |
| first = a; | |
| second = b; | |
| third = c; | |
| } | |
| T first; | |
| T second; | |
| T third; | |
| }; | |
| long long mod(long long a, long long b) | |
| { | |
| long long res=a%b; | |
| if(res < 0) return res+b; | |
| else return res; | |
| } | |
| //扩展欧几里德算法 | |
| // d = gcd(a, b) = a*x + b*y | |
| // return <d, x, y> | |
| ternary<long long> | |
| extEuclid(long long a, long long b) | |
| { | |
| ternary<long long> temp; | |
| if (b==0) { | |
| ternary<long long> k(a, 1, 0); | |
| return k; | |
| } | |
| temp=extEuclid(b, mod(a, b)); | |
| ternary<long long> res(temp.first, temp.third, temp.second - a/b*temp.third); | |
| return res; | |
| } | |
| //求a对模n的逆元a^(-1) mod n | |
| // iff { (a * x)=1 mod n } | |
| long long modInverse (long long a, long long n) | |
| { | |
| long long inverse = extEuclid(a, n).second; | |
| while(inverse<0) inverse=inverse+n; | |
| return inverse; | |
| } | |
| // a*x =b (mod n) 求x (mod n) | |
| //return a vector containing solution xi (mod n) | |
| vector<int> modLinearEquation(int a, int b, int n) | |
| { | |
| ternary<int> tmp=extEuclid(a, n); | |
| int d=tmp.first; | |
| vector<int> x; | |
| if(b%d==0) { | |
| x.resize(d); | |
| int x0 = mod(tmp.second*(b/d), n); | |
| for(int i=0; i<d; i++) | |
| x[i]=mod( x0+ i*(n/d), n); | |
| } // else no solution | |
| return x; | |
| } | |
| //ai = a mod ni for(i=1,2,3...) 求a | |
| long long chineseRemainder(vector<long long>& ai, vector<long long >& ni) | |
| { | |
| int sz = ai.size(); | |
| long long n = accumulate(ni.begin(), ni.end(), 1LL, multiplies<long long>()); // | |
| vector<long long> ci(sz); | |
| for(int i=0; i<sz; i++) { | |
| long long mi=n/ni[i]; | |
| ci[i]=mi*modInverse(mi, ni[i]); | |
| } | |
| long long sum=inner_product(ai.begin(), ai.end(), ci.begin(), 0LL); // 注意 0LL | |
| return mod(sum,n); | |
| } | |
| /* Compute and return x^power. | |
| * @return x^power */ | |
| double raise(double x, int exponent) | |
| { | |
| if (exponent < 0) return 1/raise(x, -exponent); | |
| double power = 1; | |
| // Loop to compute x^exponent. | |
| while (exponent > 0) { | |
| // Is the rightmost exponent bit a 1? | |
| if ((exponent & 1) == 1) power *= x; | |
| // Square x and shift the exponent 1 bit to the right. | |
| x *= x; | |
| exponent >>= 1; | |
| } | |
| return power; | |
| } | |
| /* return a^b (mod n) */ | |
| int modPow(int a, int b, int n) | |
| { | |
| bool bk[31]; // max b=2^31-1 | |
| for(int i=0; i<31; i++) | |
| bk[i]= b &(1<<i); | |
| int d=1; | |
| for(int i=30; i>=0; i--){ | |
| d=(d*(long long)d)%n; | |
| if(bk[i]==1) | |
| d=(d*(long long)a)%n; | |
| } | |
| return d; | |
| } | |
| /******* Shortest Path start ***********************/ | |
| // Dijkstra | |
| int shortestPath(int start, int dest, const vector<vector<ii> >& G) | |
| /* index start from 1 | |
| G.size() is the number of vertices in our graph | |
| G[i].size() is the number of vertices directly reachable from vertex with index i | |
| G[i][j].first is the index of j-th vertex reachable from vertex i | |
| G[i][j].second is the length of the edge heading from vertex i to vertex G[i][j].first | |
| return the length from index start to dest, if not reachable, return -1 | |
| */ | |
| { | |
| vector<int> D(sz(G), 987654321); | |
| priority_queue< ii,vector<ii>,greater<ii> > Q; | |
| D[start] = 0; | |
| Q.push(make_pair(0,start)); | |
| while(!Q.empty()) | |
| { | |
| ii top = Q.top(); | |
| Q.pop(); | |
| int v = top.second, d = top.first; | |
| if(v==dest) | |
| break; | |
| if(d <= D[v]) { | |
| for(int i=0;i<sz(G[v]);++i) { | |
| int v2 = G[v][i].first; | |
| int cost = G[v][i].second; | |
| if(D[v2] >(D[v] + cost)) { | |
| D[v2] = D[v] + cost; | |
| Q.push(make_pair(D[v2], v2)); | |
| } | |
| } | |
| } | |
| } | |
| return (D[dest]==987654321) ? (-1) : D[dest] ; | |
| } | |
| vector<vector<int> > floydWashall(const vector<vector<int> >& W) | |
| // index begins with 0 | |
| { | |
| int n = W.size(); | |
| vector<vector<int> > D = W; | |
| for(int k=0; k<n; k++) { | |
| for (int i=0; i<n; i++) { | |
| for(int j=0; j<n; j++) { | |
| D[i][j]=min(D[i][j], D[i][k]+D[k][j]); | |
| } | |
| } | |
| } | |
| return D; | |
| } | |
| /*********** Shortest path end **************/ | |
| /******** MST 最小生成树 start *****************/ | |
| int MST_PRIM(const vector<vector<pair<int, int> > > & G) | |
| // 邻接表表示 index start from 1 and Graph size = G.size()-1 | |
| // G[i].first is the cost, G[i].second is the adjcent vertex of i | |
| // return the minimum cost of the spanning tree or -1 if the graph is not connected | |
| { | |
| int n = G.size(); | |
| vector<int> key (n, 987654321); | |
| vector<bool> belongQ(n, 1); | |
| key[1]=0; | |
| set<pair<int, int> > Q; | |
| for(int i=1; i<n; i++) | |
| Q.insert(make_pair(key[i], i)); | |
| bool connected = true; | |
| while (!Q.empty()) { | |
| int u=Q.begin()->second; | |
| if(key[u]==987654321) { // // 非连通 | |
| connected = false; | |
| break; | |
| } | |
| Q.erase(Q.begin()); | |
| belongQ[u]=false; | |
| for(int i=0; i< G[u].size(); i++) { | |
| int v = G[u][i].second; | |
| if(belongQ[v] && G[u][i].first < key[v]) { | |
| Q.erase(Q.find(make_pair(key[v], v))); | |
| key[v]=G[u][i].first; | |
| Q.insert(make_pair(key[v], v)); | |
| } | |
| } | |
| } | |
| if(connected==false) | |
| return -1; | |
| int res=0; | |
| for(int i=1; i < n; i++) | |
| res+=key[i]; | |
| return res; | |
| } | |
| // 邻接矩阵 | |
| int G[100][100]; | |
| int MST_PRIM(int n) | |
| // adjcent matrix | |
| // index start from 0 and Graph size = G.size() | |
| // return the minimum cost of the spanning tree | |
| { | |
| vector<int> key (n, 987654321); | |
| vector<bool> belongQ(n, 1); | |
| key[0]=0; | |
| set<pair<int, int> > Q; | |
| for(int i=0; i<n; i++) | |
| Q.insert(make_pair(key[i], i)); | |
| while (!Q.empty()) { | |
| int u=Q.begin()->second; | |
| Q.erase(Q.begin()); | |
| belongQ[u]=false; | |
| for(int v=0; v< n; v++) { | |
| if(belongQ[v] && G[u][v] < key[v]) { | |
| Q.erase(Q.find(make_pair(key[v], v))); | |
| key[v]=G[u][v]; | |
| Q.insert(make_pair(key[v], v)); | |
| } | |
| } | |
| } | |
| int res=0; | |
| for(int i=0; i < n; i++) | |
| res+=key[i]; | |
| return res; | |
| } | |
| /***************** 并查集 start *****************************/ | |
| // 并查集 + Kruskal | |
| struct node | |
| { | |
| int root; | |
| int rank; | |
| }; | |
| const int poolSize=101; | |
| node nodePool[poolSize]; | |
| void makeSet(int cnt) | |
| { | |
| nodePool[cnt].root=cnt; | |
| nodePool[cnt].rank=0; | |
| } | |
| int findSet(int x) | |
| { | |
| if(x!=nodePool[x].root) | |
| nodePool[x].root = findSet(nodePool[x].root); | |
| return nodePool[x].root; | |
| } | |
| void unionSet(int x, int y) | |
| { | |
| x= findSet(x); | |
| y= findSet(y); | |
| if(x==y) return; // in the same set | |
| if(nodePool[x].rank > nodePool[x].rank ) { | |
| nodePool[y].root=x; | |
| } else { | |
| nodePool[x].root=y; | |
| if(nodePool[x].rank==nodePool[y].rank) { | |
| nodePool[y].rank++; | |
| } | |
| } | |
| } | |
| /************ 并查集 end ********************************************/ | |
| int mstKruskal(int graphSize, vector<pair<int, pair<int, int> > >& E) | |
| // E ( weight, edge) , edge = pair<int, int> | |
| // edge list index start from 0. | |
| // vertex start from 1 to graphSize | |
| // return minimum cost of the spanning tree or -1 if the graph is not connected | |
| { | |
| /* vector<pair<int, int> > mst; 最小生成树选择的边 */ | |
| int minCost = 0; | |
| for(int i=1; i<=graphSize; i++) | |
| makeSet(i); | |
| int component=graphSize; // 连通支数目 | |
| sort(E.begin(), E.end() ); // in nondecreasing order by weight | |
| for(int i=0; i<E.size(); i++) { | |
| if(findSet(E[i].second.first)!=findSet(E[i].second.second)) { | |
| minCost+=E[i].first; | |
| //mst.push_back(E[i].second); | |
| unionSet(E[i].second.first, E[i].second.second); | |
| component -- ; | |
| } | |
| } | |
| if(component!=1) return -1; // not connected graph | |
| else return minCost; | |
| //return mst; | |
| } | |
| /*********************** MST 最小生成树 end *******************/ | |
| /********************* 网络流 start *****************************/ | |
| // max flow push and relabel | |
| const int INFINITE = 987654321; | |
| const int MAX_V = 205; | |
| int V ; // number of vertices | |
| int G[MAX_V][MAX_V]; // adjacent matrix and 残留网络 | |
| int e[MAX_V]; // 溢出流 | |
| int h[MAX_V]; // 高度函数 | |
| void discharge(int u) | |
| { | |
| int min_h = INFINITE; | |
| for(int v = 0; e[u] > 0; v++) { | |
| if( v == V ) { | |
| h[u] = min_h + 1; //relabel(u); | |
| min_h = INFINITE; | |
| v = -1; | |
| } else { | |
| int df = min ( e[u], G[u][v]); | |
| if( df == 0 ) continue; | |
| else if(h[u] == h[v] + 1) { // push | |
| G[u][v] -= df; | |
| G[v][u] += df; | |
| e[u] -= df; | |
| e[v] += df; | |
| } | |
| else if( h[v] < min_h) | |
| min_h = h[v]; | |
| } | |
| } | |
| } | |
| int relabel_to_front(int s, int t) | |
| { | |
| //initilize_preflow : s; | |
| memset(h, 0, sizeof(h)); // 初始化高度函数 | |
| memset(e, 0, sizeof(e)); // 初始化溢出流 | |
| h[s] = V; | |
| for(int u = 0; u < V; u++) if(G[s][u]) { | |
| e[u] = G[s][u]; | |
| e[s] -= G[s][u]; | |
| G[u][s] = G[s][u]; | |
| G[s][u] = 0; | |
| } | |
| list<int> L; | |
| for(int i = 0; i < V; i++) if(i!=s && i!=t) { | |
| L.push_back(i); | |
| } | |
| list<int>::iterator it = L.begin(); | |
| while( it != L.end() ) { | |
| int u = *it; | |
| int old_height = h[u]; | |
| discharge(u); | |
| if(h[u] > old_height){ // move u to the front of list L | |
| L.erase(it); | |
| L.push_front(u); | |
| it = L.begin(); | |
| } | |
| it ++; | |
| } | |
| int res = 0; | |
| for(int i = 0; i < V; i++) | |
| res += G[i][s]; | |
| return res; | |
| } | |
| int main() | |
| { | |
| // set the MAX_V | |
| int n, m; // the number of vertex, edge | |
| //freopen("D:\\input.txt", "r", stdin); | |
| while(scanf("%d %d", &m, &n)!=EOF) { | |
| V = n; // Set V to the number of vertices | |
| memset(G, 0, sizeof(G)); | |
| int s, e, c; | |
| for(int i=0; i<m; i++) { | |
| scanf("%d %d %d", &s, &e, &c); | |
| if( e == 1 || s==e) continue; // !!!!!!!!!!!!! | |
| G[s-1][e-1] += c; | |
| } | |
| printf ("%d\n", relabel_to_front(0, n-1) ); | |
| } | |
| return 0; | |
| } | |
| /************ BFS 找增流路径 ****************************/ | |
| const int INFINITE = 987654321; | |
| const int MAX_V = 305; | |
| int V; // number of vertices | |
| int G[MAX_V][MAX_V]; | |
| /* | |
| Initially the residual network is just the original network. | |
| We will not store the flows along the edges explicitly, | |
| but it's easy to figure out how to find them upon the termination | |
| of the algorithm: for each edge x-y in the original network the flow | |
| is given by the capacity of the backward edge y-x in the residual network. | |
| Be careful though; if the reversed arc y-x also exists in the original | |
| network, this will fail, and it is recommended that the initial capacity of each | |
| arc be stored somewhere, and then the flow along the edge is the difference | |
| between the initial and the residual capacity. | |
| */ | |
| /** | |
| * Edmonds-Karp | |
| * find the Augmenting-Path by BFS | |
| * Complexity: O(V*M) where V is the number of vertices | |
| * and M is the number of edges in the Graph | |
| * @param source - the index of source node | |
| * @param sink - the index of sink node | |
| * return the Augmenting-Path G. | |
| */ | |
| int find_path(int source, int sink) | |
| { | |
| bool visited [V]; | |
| memset(visited, 0, sizeof(visited)); | |
| // 'from[x]' is the previous vertex visited | |
| // in the shortest path from the source to x | |
| int from [V] ; | |
| memset(from, -1, sizeof(from)); | |
| queue<int> Q; | |
| Q.push(source); | |
| visited[source] = true; | |
| bool found = false; | |
| while(!Q.empty()) { | |
| int where = Q.front(); Q.pop(); | |
| for(int next = 0; next < V; next++) if(G[where][next] > 0) { | |
| if( visited[next] == false) { | |
| Q.push(next); | |
| visited[next] = true; | |
| from[next] = where; | |
| if(next == sink) { // found the Augmenting-Path | |
| found = true; | |
| break ; | |
| } | |
| } | |
| } // end for | |
| if(found){ | |
| break; | |
| } | |
| } // end while | |
| // compute the path capacity | |
| int where = sink; | |
| int path_capacity = INFINITE; | |
| while( from[where] > -1 ) { | |
| int prev = from[where] ; // the previous vertex | |
| path_capacity = min(path_capacity, G[prev][where]); | |
| where = prev; | |
| } | |
| // update the residual network | |
| // if no path is found the while loop will not be entered ( from[where] = -1) | |
| where = sink; | |
| while(from[where] > -1) { | |
| int prev = from[where]; | |
| G[prev][where] -= path_capacity; | |
| G[where][prev] += path_capacity; | |
| where = prev; | |
| } | |
| if(path_capacity == INFINITE) // no path is found | |
| return 0; | |
| else | |
| return path_capacity; | |
| } | |
| int max_flow(int source, int sink) { | |
| int result = 0; | |
| while( true ) { | |
| int path_capacity = find_path(source, sink); | |
| if(path_capacity == 0) | |
| break; | |
| result += path_capacity; | |
| } | |
| return result; | |
| } | |
| int main() | |
| { | |
| int n, m; | |
| int a, b; | |
| while( scanf("%d %d", &n, &m), n!=0 || m!=0) { | |
| V = n+2; | |
| memset(G, 0, sizeof(G)); | |
| for(int i = 1; i<=n; i++) { | |
| scanf("%d", &b); | |
| if(b) { | |
| G[0][i] = 1; | |
| } | |
| else { | |
| G[i][n+1] = 1; | |
| } | |
| } | |
| for(int i= 0; i<m; i++) { | |
| scanf("%d %d", &a, &b); | |
| G[a][b] = 1; | |
| G[b][a] = 1; | |
| } | |
| int res = max_flow(0, n+1); | |
| printf("%d\n", res); | |
| } | |
| return 0; | |
| } | |
| /****************** max flow end *********************/ | |
| /***************** Trie start *****************/ | |
| struct Trie { | |
| int prefixes, words; | |
| Trie* edges[26]; | |
| Trie() // constructor | |
| { | |
| //prefixes=0; | |
| words=0; | |
| for(int i=0; i<26; i++) { | |
| edges[i] = NULL; | |
| } | |
| return; | |
| } | |
| // ~Trie() | |
| // { | |
| // for(int i=0; i<10; i++) | |
| // if(edges[i]!=NULL) | |
| // delete edges[i]; | |
| // } | |
| }; | |
| void addWord(Trie &vertex, char* word) | |
| { | |
| if (word[0]=='\0') { // word is empty | |
| vertex.words ++; | |
| } else { | |
| //vertex.prefixes ++; | |
| char k = word[0]; | |
| if(vertex.edges[k - 'a']==NULL) { | |
| vertex.edges[k- 'a'] = new Trie(); | |
| } | |
| word ++; // cut leftmost char; | |
| addWord( *(vertex.edges[k - 'a']), word ); | |
| } | |
| } | |
| int countWords(Trie &vertex, char* word) | |
| { | |
| if (word[0]=='\0') // word is empty | |
| return vertex.words; | |
| else { | |
| char k=word[0]; | |
| if(vertex.edges[k-'a']==NULL) | |
| return 0; | |
| else { | |
| word++; | |
| return countWords(*(vertex.edges[k-'a']), word); | |
| } | |
| } | |
| } | |
| /* | |
| pre-condition: the word is already in the trie. | |
| post: words count -- | |
| */ | |
| void removeWord(Trie &vertex, char* word) | |
| { | |
| if (word[0]=='\0') // word is empty | |
| vertex.words--; | |
| else { | |
| char k=word[0]; | |
| word++; | |
| return removeWord(*(vertex.edges[k-'a']), word); | |
| } | |
| } | |
| countPrefixes(vertex, prefix) | |
| { | |
| k=firstCharacter(prefix) | |
| if isEmpty(word) | |
| return vertex.prefixes | |
| else if notExists(edges[k]) | |
| return 0 | |
| else | |
| cutLeftmostCharacter(prefix) | |
| return countWords(edges[k], prefix) | |
| } | |
| /************* Trie end ************************************************************/ | |
| bool dfsVisit(const vector< vector<int> >& G, vector<int>& color, vector<int>&seq, int u) | |
| { | |
| color[u]=1; // gray | |
| //time++; | |
| for(int i=0; i<G[u].size(); i++) { | |
| if(color[G[u][i]]==1) | |
| return true; | |
| if(color[G[u][i]]==0) | |
| if(dfsVisit(G, color, seq, G[u][i])) | |
| return true; | |
| } | |
| color[u]=2; //black | |
| //f[u]=++time; | |
| seq.push_back(u); | |
| return false; | |
| } | |
| // 有向图 // 拓扑排序 + 判断是否有回路 | |
| //return true for circle | |
| bool dfs(const vector< vector<int> >& G, vector<int>&seq) | |
| { | |
| vector<int> color(G.size(), 0); | |
| for(int i=1; i< G.size(); i++) //G[v]是v的邻接点集合 | |
| if(color[i]==0) | |
| if(dfsVisit(G, color, seq, i)) | |
| return true; | |
| return false; | |
| } | |
| //判断连通枝是否有回路 (无向图) | |
| bool dfs2(const vector<vector<int> >& G, vector<bool>& visited, int parent, int v) | |
| { | |
| visited[v]=true; | |
| for(int i=0; i< G[v].size(); i++) //G[v]是v的邻接点集合 | |
| if(G[v][i]!=parent) { | |
| if(visited[G[v][i]]==true) | |
| return true; | |
| else | |
| dfs2(G, visited, v, G[v][i]); | |
| } | |
| return false; | |
| } | |
| 整数拆分（不可重复） | |
| /** | |
| * Description: 整数拆分(不可重复) 给定一个整数n(3~500)，试求这个整数的拆分方式 | |
| * (不可重复，且至少包含两个元素)。如6的拆分方式有1 5、2 4、1 2 3 三种。 | |
| * 定义数组dat[][] dat[i][j]表示对整数i进行拆分，其中所拆分的数的最大值 | |
| * 为j。则有递推式 | |
| * i=0||j=0 dat[i][j]=0; | |
| * i>(1+j)*j/2 dat[i][j]=0; | |
| * i=(1+j)*j/2 dat[i][j]=1; | |
| * i<(1+j)*j/2 | |
| * i<j dat[i][j]=dat[i][i]; | |
| * i=j dat[i][j]=dat[i][j-1]+1; | |
| * i>j dat[i][j]=dat[i-j][j-1]+dat[i][j-1]; | |
| * input output | |
| * 6 3 | |
| * 25 141 | |
| * 500 732986521245023 | |
| */ | |
| /*****************************************************************************/ | |
| int KMP(const string& txt, const string& substr) | |
| { | |
| int n = txt.length(); | |
| int m = substr.length(); | |
| int* prefix = new int[m]; | |
| prefix[0] = -1; | |
| for (int k = -1, q = 1; q < m; q ++) | |
| { | |
| while ( k >= 0 && substr[k+1] != substr[q]) | |
| k = prefix[k]; | |
| if (substr[k+1] == substr[q]) | |
| k++; | |
| prefix[q] = k; | |
| } | |
| for (int q = -1, i = 0; i < n; i++) { | |
| while (q >= 0 && substr[q+1] != txt[i]) | |
| q = prefix[q]; | |
| if ( substr[q+1] == txt[i]) | |
| q ++; | |
| if (q == m-1) { | |
| //return i - m + 1; | |
| cout<<"Pattern occurs with shift" << i - m + 1 <<endl; | |
| q = prefix[q]; | |
| } | |
| } | |
| delete[] prefix; | |
| return -1; | |
| } | |
| /******************** BigInteger start *********************************************************/ | |
| const int base = 1000000000; | |
| const int num_digit = 9; // num_digit = lg(base) | |
| const int MAXN = 127; // the maximum number can be as big as ( base * MAXN ) | |
| /** | |
| * s[high] ... s[0] | |
| * 高位 ... 低位 | |
| */ | |
| struct Big { | |
| int high; | |
| int s[MAXN]; | |
| Big () { high = 0; s[0] = 0;} | |
| Big (const char* str) { *this = str ;} | |
| Big operator = (int i) { high = 0; s[0] = i;} | |
| Big operator = (const char* str) { | |
| int str_len = strlen(str) ; | |
| high = (str_len - 1) / num_digit ; | |
| memset(s, 0, sizeof(int)*(high+1)); | |
| for(int i=0; i < str_len; i++) { | |
| int k = (str_len - 1 - i)/num_digit ; | |
| s[k] = s[k] * 10 + str[i] - '0'; | |
| } | |
| while( high && !s[high]) high-- ; // trim the leading zero | |
| return *this; | |
| } | |
| }; | |
| /** | |
| * depends: num_digit | |
| */ | |
| void print(const Big &a) | |
| { | |
| printf("%d", a.s[a.high]); | |
| for(int i=a.high-1 ; i>=0; i--) | |
| printf("%09d", a.s[i]); // 9 = num_digit | |
| } | |
| int length(const Big &a) // 10进制位长度 | |
| { | |
| int len = a.high * num_digit; | |
| for(int pow10 = 1; pow10 <= a.s[a.high]; len ++) | |
| pow10 *= 10; | |
| return len; | |
| } | |
| /** | |
| * uses: length() | |
| * depends: num_digit | |
| */ | |
| char* toString(const Big &a) | |
| { | |
| int len = length(a); | |
| char* str = new char[ len + 1]; str[len] = 0; | |
| sprintf(str, "%d", a.s[a.high]); | |
| int pos = len - num_digit * a.high; | |
| for(int i = a.high - 1; i >= 0; i--){ | |
| sprintf(str + pos, "%09d", a.s[i]); // 9 = num_digit | |
| pos += num_digit; | |
| } | |
| return str; | |
| } | |
| Big operator + (const Big &a, const Big &b) | |
| { | |
| Big c; | |
| int i; | |
| for(i = 0; i <= a.high || i<= b.high || c.s[i]; i++) { | |
| if( i <= a.high) c.s[i] += a.s[i]; | |
| if( i <= b.high) c.s[i] += b.s[i]; | |
| c.s[i+1] = c.s[i] / base; | |
| c.s[i] %= base; | |
| } | |
| c.high = i - 1; | |
| return c; | |
| } | |
| // pre-condition: a > b | |
| Big operator - (const Big &a, const Big &b) | |
| { | |
| Big c; | |
| for(int i= 0, sub = 0; i<= a.high; i++) { | |
| c.s[i] = a.s[i] - sub; | |
| if( i <= b.high) | |
| c.s[i] -= b.s[i]; | |
| if( c.s[i] < 0) { | |
| sub = 1; | |
| c.s[i] += base; | |
| } | |
| else sub = 0; | |
| } | |
| for(c.high = a.high; c.high && !c.s[c.high]; c.high--) ; // trim the leading zero | |
| return c; | |
| } | |
| Big operator * (const Big &a, const Big &b) | |
| { | |
| Big c; | |
| c.high = a.high + b.high + 1; | |
| memset(c.s, 0, sizeof(int)*(c.high + 1)); | |
| int g = 0; | |
| for(int k=0; k <= c.high; k++) { | |
| long long tmp = g; | |
| for(int i = max( k - b.high, 0); i <= k && i<= a.high; i++) | |
| tmp += (long long) a.s[i]*(long long)b.s[k-i]; | |
| g = (int) (tmp/base); | |
| c.s[k] = (int) (tmp % base); | |
| } | |
| while( c.high && !c.s[c.high]) // trim the leading zero | |
| c.high --; | |
| return c; | |
| } | |
| int cmp(const Big &a, const Big &b) | |
| { | |
| if( a.high > b.high) | |
| return 1; | |
| else if(a.high < b.high) | |
| return -1; | |
| for(int i = a.high; i>=0; i--) { | |
| if(a.s[i] > b.s[i]) | |
| return 1; | |
| else if(a.s[i] < b.s[i]) | |
| return -1; | |
| } | |
| return 0; | |
| } | |
| /** | |
| * uses: cmp, operator *, - | |
| */ | |
| Big operator / (const Big &a, const Big &b) | |
| { | |
| Big q, r (a); | |
| Big p; p.high = a.high; | |
| for(int i=p.high-1; i>=0; i--) | |
| p.s[i] = 0; | |
| Big t, toSub; | |
| for(int cur = a.high; cur>=0; p.high--,cur--) { // try each 'Bit' | |
| bool flag = false; | |
| int lo = 0, hi = base-1; | |
| while(lo < hi) { // (true...true,false...false) find last true | |
| int mid = lo + (hi - lo + 1)/2 ; // rounds up | |
| p.s[p.high] = mid; | |
| t = p * b; | |
| if(cmp (t, r) > 0) // is false | |
| hi = mid - 1; | |
| else { | |
| flag = true; | |
| toSub = t; | |
| lo = mid; | |
| } | |
| } | |
| if( flag ) | |
| r = r - toSub; | |
| q.s[cur] = lo; | |
| } | |
| // trim the leading zero | |
| for( q.high = a.high; q.high && ! q.s[q.high]; q.high--); | |
| return q; | |
| } | |
| /** | |
| * uses: cmp, operator +, / (or and *) | |
| */ | |
| Big sqrt(const Big &n) | |
| { | |
| Big x, y; | |
| // set the initial value to iterate | |
| if(n.high % 2 == 0) { | |
| y.high = n.high/2; | |
| y.s[y.high] = (int)sqrt(double(n.s[n.high])) + 1; | |
| } | |
| else { | |
| long long u = base *(long long) n.s[n.high] + (long long) n.s[n.high-1]; | |
| y.high = (n.high - 1)/2; | |
| y.s[y.high] = (int)sqrt(double(u)) + 1; | |
| if(y.s[y.high] > base) | |
| { | |
| y.s[y.high]-= base; | |
| y.high ++; | |
| y.s[y.high] = 1; | |
| } | |
| } | |
| Big two("2"); | |
| do { | |
| x = y; | |
| y = (x + n/x) / two; | |
| } while( cmp(y, x) < 0); | |
| return x; | |
| } | |
| /** | |
| * a / b = q | |
| * a % b = r | |
| * uses: cmp, operator- | |
| * warning: to use this version, set base = 10 !! | |
| */ | |
| void divide (const Big &a, const Big &b, Big &q, Big &r) | |
| { | |
| int i , j ; | |
| for ( i = a.high; i >= 0; i --){ | |
| if (!( r.high == 0 && r.s[0] == 0)) { // r != 0 | |
| for ( j = r.high; j >=0; j --) // remainder array shift to left by 1 | |
| r.s [j+1] = r.s [j]; | |
| ++ r.high; | |
| } | |
| r.s [0] = a.s [i]; | |
| q.s [i] = 0; | |
| while ( ( j = cmp (r , b )) >= 0) { | |
| r = r - b; // call the overloaded operator - | |
| q.s [i]++; | |
| if ( j == 0) break ; | |
| } | |
| } | |
| // trim the leading zero | |
| for( q.high = a.high; q.high && ! q.s[q.high]; q.high--); | |
| } | |
| /**^^^^^^^^^^^ BigInteger ^^^^^^^^^^ */ | |
| /*********************************************************/ | |
| /* // Stoer-Wagner Minimum Cut // | |
| * | |
| * MAIN FUNCTION: minCut( n ) | |
| * Takes an undirected, weighted graph and returns the weight | |
| * of the minimum cut in it. A cut is a set of edges that, | |
| * when removed, disconnects the graph. A minimum cut is a | |
| * cut of minimum total weight. | |
| * ALGORITHM: | |
| * This is a O(n^3) implementation of the Stoer-Wagner | |
| * deterministic algorithm (no randomization is required). | |
| * FIELD TESTING: | |
| * - UVa 10989: Bomb, Divide and Conquer | |
| **/ | |
| // Maximum number of vertices in the graph | |
| #define NN 256 | |
| // Maximum edge weight (MAXW * NN * NN must fit into an int) | |
| #define MAXW 1000 | |
| // Adjacency matrix and some internal arrays | |
| int g[NN][NN], v[NN], w[NN], na[NN]; | |
| bool a[NN]; | |
| int minCut( int n ) | |
| { | |
| // init the remaining vertex set | |
| for( int i = 0; i < n; i++ ) v[i] = i; | |
| // run Stoer-Wagner | |
| int best = MAXW * n * n; | |
| while( n > 1 ) | |
| { | |
| // initialize the set A and vertex weights | |
| a[v[0]] = true; | |
| for( int i = 1; i < n; i++ ) | |
| { | |
| a[v[i]] = false; | |
| na[i - 1] = i; | |
| w[i] = g[v[0]][v[i]]; | |
| } | |
| // add the other vertices | |
| int prev = v[0]; | |
| for( int i = 1; i < n; i++ ) | |
| { | |
| // find the most tightly connected non-A vertex | |
| int zj = -1; | |
| for( int j = 1; j < n; j++ ) | |
| if( !a[v[j]] && ( zj < 0 || w[j] > w[zj] ) ) | |
| zj = j; | |
| // add it to A | |
| a[v[zj]] = true; | |
| // last vertex? | |
| if( i == n - 1 ) | |
| { | |
| // remember the cut weight | |
| best <?= w[zj]; | |
| // merge prev and v[zj] | |
| for( int i = 0; i < n; i++ ) | |
| g[v[i]][prev] = g[prev][v[i]] += g[v[zj]][v[i]]; | |
| v[zj] = v[--n]; | |
| break; | |
| } | |
| prev = v[zj]; | |
| // update the weights of its neighbours | |
| for( int j = 1; j < n; j++ ) if( !a[v[j]] ) | |
| w[j] += g[v[zj]][v[j]]; | |
| } | |
| } | |
| return best; | |
| } | |
| int main() | |
| { | |
| // read the graph's adjacency matrix into g[][] | |
| // and set n to equal the number of vertices | |
| int n, answer = minCut( n ); | |
| return 0; | |
| } | |
| /***************** 二分图最大匹配 ******************/ | |
| const int MAX_N = 501; | |
| int G[MAX_N][MAX_N]; | |
| int n; | |
| // in this arrays we keep matches found to every row and column | |
| int row_match[MAX_N], col_match[MAX_N]; | |
| bool visited[MAX_N]; | |
| bool find_match(int where) { | |
| // the previous column was not matched | |
| if (where == -1) | |
| return true; | |
| for (int i = 0; i < n; ++ i) if(G[where][i]) { | |
| int match = i; | |
| if (visited[match] == false) { | |
| visited[match] = true; | |
| if (find_match(col_match[match])) { | |
| col_match[match] = where; | |
| row_match[where] = match; | |
| return true; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| int match () | |
| { | |
| memset(row_match, -1, sizeof(row_match)); | |
| memset(col_match, -1, sizeof(col_match)); | |
| int matched = 0; | |
| for(int i =0; i<n; i++) { | |
| memset(visited, 0, sizeof(visited)); | |
| matched += find_match(i); | |
| } | |
| return matched ; | |
| } | |
| int main() | |
| { | |
| memset(G, 0, sizeof(G)); | |
| // input G | |
| int res = match(); | |
| } | |
| /***************** best match start ******************/ | |
| const int INF = 987654321; | |
| const int SIZE = 101; | |
| int nx, ny; // number of x and y | |
| int label_x[SIZE], label_y[SIZE]; | |
| int match_x[SIZE], match_y[SIZE]; | |
| bool seen_x[SIZE], seen_y[SIZE]; | |
| int weight[SIZE][SIZE]; | |
| bool find_path(int u) | |
| { | |
| seen_x[u] = true; | |
| for(int v = 0; v < ny; v++) { | |
| if( !seen_y[v] && label_x[u] + label_y[v] == weight[u][v] ) { | |
| seen_y[v] = true; | |
| if(match_y[v] == -1 || find_path(match_y[v] ) ) { | |
| match_x[u] = v; | |
| match_y[v] = u; | |
| return true; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| int bestMatch() | |
| { | |
| for(int i = 0; i<nx; i++) { | |
| label_x[i] = - INF; | |
| for(int j=0; j<ny; j++) | |
| label_x[i] = max(label_x[i], weight[i][j]); | |
| } | |
| memset(label_y, 0, sizeof(label_y)); | |
| memset(match_x, -1, sizeof(match_x)); | |
| memset(match_y, -1, sizeof(match_y)); | |
| memset(seen_x, false, sizeof(seen_x)); | |
| memset(seen_y, false, sizeof(seen_y)); | |
| for(int u = 0; u < nx; u ++ ) if(match_x[u]==-1) {// x[u] not matched | |
| while(!find_path(u)) { | |
| int d = INF; | |
| for(int i = 0; i< nx; i++) if(seen_x[i]) // for each x vertex seen in find_path | |
| for(int j =0; j<ny; j++) if(!seen_y[j]) // for each y vertex connecting to i and not seen in find_path | |
| d = min(d, label_x[i] + label_y[j] - weight[i][j]); | |
| // modify the label | |
| for(int i = 0; i<nx; i++) | |
| if(seen_x[i]) | |
| label_x[i] -= d; | |
| for(int i = 0; i<ny; i++) | |
| if(seen_y[i]) | |
| label_y[i] += d; | |
| memset(seen_x, false, sizeof(seen_x)); | |
| memset(seen_y, false, sizeof(seen_y)); | |
| } | |
| } | |
| int res = 0; | |
| for(int j=0; j<ny; j++) { | |
| res += weight[match_y[j]] [j]; | |
| // cout<<match_y[j]<<" -> " <<j<<endl; | |
| } | |
| return res; | |
| } | |
| int main() | |
| { | |
| int n, m; // row col | |
| while(scanf("%d %d", &n, &m), n!=0 || m!=0) { | |
| nx = n; | |
| ny = m; | |
| memset(weight, 0, sizeof(weight)); | |
| for(int i=0; i<n; i++) | |
| for(int j=0; j<m; j++) | |
| cin>>weight[i][j]; | |
| printf("%d\n", bestMatch()); | |
| } | |
| return 0; | |
| } | |
| /***************** Best Match end *******************/ | |
| /***************** binary search start *****************/ | |
| // binary search find the first true | |
| binary_search(lo, hi, p): | |
| while lo < hi: | |
| mid = lo + (hi-lo)/2 | |
| if p(mid) == true: | |
| hi = mid | |
| else: | |
| lo = mid+1 | |
| if p(lo) == false: | |
| complain // p(x) is false for all x in S! | |
| return lo // lo is the least x for which p(x) is true | |
| // find the last x for which p(x) is false | |
| binary_search(lo, hi, p): | |
| while lo < hi: | |
| mid = lo + (hi-lo+1)/2 // rounds up | |
| if p(mid) == true: | |
| hi = mid-1 | |
| else: | |
| lo = mid | |
| if p(lo) == true: | |
| complain // p(x) is true for all x in S! | |
| return lo // lo is the greatest x for which p(x) is false | |
| /******* binary search end *********/ | |
| //找欧拉回路 或开欧拉迹 | |
| // 开欧拉迹的话要指定 start为奇数度的点 | |
| vector<int> EulerCircle (list<int> * G, int start=0) | |
| { | |
| int n= 7; | |
| int edge = 0; | |
| for (int i = 0; i < n; i ++) { | |
| int degree = G [i].size (); | |
| edge += degree; | |
| } | |
| // 边数= 度数 / 2，path保持欧拉路上点的顺序, n+1个 | |
| vector<int> path (edge / 2 + 1); | |
| stack <int> s; | |
| int p = 0, i = start; | |
| s.push(i); | |
| do { | |
| if (G [i].empty ()) { | |
| do { | |
| s.pop (); | |
| path [p++] = i; | |
| } while (!s.empty () && (i = s.top (), G [i].empty ())); | |
| } | |
| else { | |
| int t = *(G [i].begin ()); | |
| G [i].erase(G [i].begin ()); | |
| G [t].erase ( find (G [t].begin (), G [t].end (), i)); | |
| s.push (t); | |
| i = t; | |
| } | |
| } while ( !s.empty() ); | |
| return path; | |
| } | |
| bool visited[7]; | |
| void dfs(list<int>* g, int v) | |
| { | |
| visited[v]=true; | |
| for(list<int>::iterator itr=g[v].begin(); itr!=g[v].end(); itr++) | |
| if(!visited[*itr]) | |
| dfs(g, *itr); | |
| } | |
| /******** 欧拉路径 end ******************/ | |
| /********* 计算几何 start ************/ | |
| // tags : | |
| // 向量垂直 -- isPerpendicular | |
| // 点积 -- dot | |
| // 叉积 -- cross | |
| // 点到点距离 -- ppDistance | |
| // 点到直线(段)距离 -- linePointDist | |
| // 多边形面积 -- polygonArea | |
| // 直线相交 -- lineIntersect | |
| // 两点坐标确定一般式直线 | |
| // 3点确定一个圆 | |
| // 点关于直线的对称 | |
| // 点关于另外一点旋转x° | |
| // 凸包 | |
| const double PI = acos(-1); | |
| const double epsilon = 1e-10; | |
| struct Vector { | |
| double x, y; | |
| inline Vector () {} // default constructor | |
| inline Vector(double a, double b): x(a), y(b) {} // constructor | |
| inline Vector operator + (const Vector &a) { return Vector(x + a.x, y + a.y); } | |
| inline Vector operator - (const Vector &a) { return Vector(x - a.x, y - a.y); } | |
| inline bool operator == (const Vector & v) { return (x == v.x && y == v.y); } | |
| }; | |
| typedef Vector Point; | |
| /** | |
| * @return true if the two Vector a and b are Perpendicular | |
| * pre: a and b are nonzero | |
| */ | |
| bool isPerpendicular(Vector a, Vector b) { | |
| return (abs(a.x * b.x + a.y * b.y) < epsilon); | |
| } | |
| /** | |
| * @return the dot product of A and B, that is |A||B|Cos(θ) | |
| * where |θ| is the angle between the two vectors | |
| */ | |
| double dot(Vector A, Vector B) { | |
| return A.x * B.x + A.y * B.y; | |
| } | |
| /** | |
| * @return the cross product of A and B, that is A x B = |A||B|Sin(θ), | |
| * where |θ| is the angle between the two vectors | |
| * if A is less than 180 degrees clockwise from B, the value of theta is positive. | |
| */ | |
| double cross(Vector A, Vector B) { | |
| return A.x * B.y - B.x * A.y; | |
| } | |
| double cross(Point A, Point B, Point O) | |
| { | |
| return (A.x - O.x)*(B.y - O.y) - | |
| (A.y - O.y)*(B.x - O.x); | |
| } | |
| //Compute the distance from Point A to Point B | |
| double ppDistance(Point A, Point B) { | |
| double d1 = A.x - B.x; | |
| double d2 = A.y - B.y; | |
| return sqrt(d1 * d1 + d2 * d2); | |
| } | |
| /** | |
| * Compute the distance from AB to C | |
| * @param isSegment true if AB is a segment, not a line | |
| * @return the distance from AB to C | |
| */ | |
| double linePointDist(Point A, Point B, Point C, bool isSegment) { | |
| Vector ab (B.x - A.x, B.y - A.y); // AB | |
| Vector bc (C.x - B.x, C.y - B.y); // BC | |
| Vector ac (C.x - A.x, C.y - A.y); // AC | |
| Vector ba (A.x - B.x, A.y - B.y); // BA | |
| // 利用三角形面积相等 ab * ac = dist * |AB| | |
| double dist = cross(ab, ac) / ppDistance(A, B); // cross product value may be negative | |
| if (isSegment) { | |
| double dot1 = dot(ab, bc); | |
| if (dot1 > 0) | |
| return ppDistance(B, C); | |
| double dot2 = dot(ba, ac); | |
| if (dot2 > 0) | |
| return ppDistance(A, C); | |
| } | |
| return abs(dist); | |
| } | |
| /** | |
| * @param p -- the coordinates as a 2-D array | |
| * @return the area of a polygon | |
| */ | |
| double polygonArea(Point p[]) { | |
| double area = 0; | |
| int N = sizeof(p)/sizeof(Point); // p.length | |
| //We will triangulate the polygon | |
| //into triangles with points p[0],p[i],p[i+1] | |
| for (int i = 1; i + 1 < N; i++) { | |
| Vector A (p[i].x - p[0].x, p[i].y - p[0].y ); | |
| Vector B (p[i+1].x - p[0].x, p[i+1].y - p[0].y ); | |
| area += cross(A, B); | |
| } | |
| return abs(area / 2.0); | |
| } | |
| /** | |
| * given two points (x1, y1), (x2, y2), define a line: Ax + By = C, where | |
| * A = y2-y1 | |
| * B = x1-x2 | |
| * C = A*x1+B*y1 | |
| */ | |
| /** | |
| * the two line are given as A1*X + B1*Y = C1 | |
| * A2*X + B2*Y = C2 | |
| * @return the point at which the two lines intersect | |
| * if both are line segments, You should check min(x1,x2) <= x <= max(x1,x2), | |
| * and do the same thing for y, where sgement goed from (x1,y1) to (x2, y2) | |
| */ | |
| Point lineIntersect(double A1, double B1, double C1, double A2, double B2, double C2) | |
| { | |
| double det = A1*B2 - A2*B1; | |
| /* if(det == 0){ | |
| cout <<"Lines are parallel " << endl; | |
| } | |
| else | |
| */ | |
| { | |
| double x = (B2*C1 - B1*C2)/det; | |
| double y = (A1*C2 - A2*C1)/det; | |
| return Point(x, y); | |
| } | |
| } | |
| /** | |
| * given three Points, define a circle | |
| * 圆心: AB, BC, 垂直平分线交点I | |
| * 垂直平分线: Ax+By=C -> -Bx+Ay=D | |
| * to find D: A,B 中点代入-Bx+Ay=D | |
| * 半径r = ppDistance(I, A) | |
| * findCircle(Point A, Point B, Point C) | |
| * */ | |
| /** | |
| * Reflection: | |
| * if the line of reflection is given as Ax+By=C, | |
| * then the line perpendicular to it is: -Bx+Ay=D. | |
| * To find D, we simply plug in the coordinates for X. | |
| * Now, we can find the intersection of the two lines at Y, and then find X' = Y - (X - Y). | |
| */ | |
| /** | |
| * Rotation | |
| * Imagine that we want to rotate one point around another, counterclockwise by θ degrees. | |
| * For simplicity, lets assume that we are rotating about the origin. | |
| * In this case, we can find that x' = x Cos(θ) - y Sin(θ) and y' = x Sin(θ) + y Cos(θ). | |
| * If we are rotating about a point other than the origin, | |
| * we can account for this by shifting our coordinate system | |
| * so that the origin is at the point of rotation, | |
| * doing the rotation with the above formulas, | |
| * and then shifting the coordinate system back to where it started. | |
| */ | |
| /** | |
| * Convex Hull | |
| */ | |
| Point First; // 凸包第一个点 | |
| bool cmp(Point a, Point b) | |
| { | |
| double prod = cross(a, b, First); | |
| if(prod < 0) return false; | |
| else if(fabs(prod) < epsilon) { | |
| double dist1 = ppDistance(a, First); | |
| double dist2 = ppDistance(b, First); | |
| return dist1 < dist2; | |
| } | |
| return true; | |
| } | |
| /** | |
| * @param Q - [in] the set of points | |
| * @param n - [in] number of points in Q | |
| * @param CH - [out] the vertices of CH(Q), in counterclockwise order | |
| * @param nv - [out] number of points of CH(Q) | |
| * @TODO: | |
| 1。3点共线 第一条边和最后一条边都有3点共线 就不能用距离值来把中间点直接去掉了 | |
| 2。关于当前边进入原凸包的情况 要直接跳过 | |
| * | |
| */ | |
| void Graham_scan_convex_hull(Point Q[], int n, Point CH[], int &nv) | |
| { | |
| // find the point with the minimum y-coordinate; | |
| int k=0; | |
| for(int i=1; i<n; i++) | |
| if ( Q[i].y < Q[k].y || | |
| ( Q[i].y == Q[k].y) && ( Q[i].x < Q[k].x) ) | |
| k=i; | |
| swap(Q[0], Q[k]); | |
| First = Q[0]; | |
| sort(Q+1, Q+n, cmp); | |
| memcpy(CH, Q, 3*sizeof(Point)); | |
| int top = 2; | |
| for (int i=3; i<n; i++) | |
| { | |
| while (cross(Q[i], CH[top], CH[top-1]) >=0 ) | |
| top--; | |
| CH[++top] = Q[i]; | |
| } | |
| nv =top+1; | |
| } | |
| /********** 计算几何 end ************/ | |
| /********** 归并排序. 求逆序 ******************/ | |
| int a[500000]; | |
| int t[500000]; | |
| long long res; | |
| void sort(int l , int r) | |
| { | |
| if(l >= r) return ; | |
| int m = ( l + r) >> 1; | |
| sort (l , m); | |
| sort (m+1 , r); | |
| // merge [l,m] and [m+1,r] | |
| int i = l , j = m+1 , c = l; | |
| while (i <= m || j <= r) | |
| if(j > r || ( i <= m && a[i] <= a[j]) ) | |
| t[c++] = a[i++]; | |
| else | |
| { | |
| t[c++] = a[j++]; | |
| res += (m - i + 1); | |
| } | |
| // copy back | |
| for(i = l; i <= r; i ++) a[i] = t[i]; | |
| } | |
| /***************** 高斯消元 线性方程组 *****************/ | |
| double A[101][101]; | |
| double B[101]; | |
| double X[101]; | |
| /** | |
| * input: A[1..m], B[1..m] | |
| * output: X[0..m-1] | |
| * A * X = B | |
| */ | |
| void gauss(int m, double eps=1e-15) | |
| { | |
| // [cof con]=[A B] | |
| int p, i, j; | |
| double * * cof=new double *[m]; // cof = A | |
| for (i=0; i<m; i++) { | |
| cof[i]=new double[m]; | |
| for(j=0; j<m; j++) | |
| cof[i][j] = A[i+1][j+1]; | |
| } | |
| double * con = new double[m]; | |
| memcpy(con, B+1, m*sizeof(double)); | |
| for (p=0; p<m-1; p++) { // 消元, 列p | |
| // find major element | |
| int Max=p; | |
| for (j=p+1; j<m; j++) // 这一列找出绝对值最大的做主元 | |
| if (fabs(cof[Max][p]) < fabs(cof[j][p])) | |
| Max=j; | |
| if (fabs(cof[Max][p])<eps) throw "Coefficient matrix is odd"; | |
| // apply row switching when necessary | |
| if (Max!=p) { | |
| std::swap(cof[Max], cof[p]); | |
| std::swap(con[Max], con[p]); | |
| } | |
| // elimination | |
| for (i=p+1; i<m; i++) { // p下面的每一行i | |
| double rate=cof[i][p]/cof[p][p]; | |
| for (j=p; j<m; j++) // 第 i 行, 每一个数 | |
| cof[i][j]-=rate*cof[p][j]; // 第i行减(第p行的*系数rate) | |
| con[i]-=rate*con[p]; | |
| } | |
| } | |
| // back-tracing the unknowns | |
| for (p=m-1; p>0; p--) { | |
| X[p]=con[p]/cof[p][p]; | |
| for (j=1; j<=p; j++) { | |
| con[p-j]-=cof[p-j][p]*X[p]; | |
| cof[p-j][p]=0.0; | |
| } | |
| } | |
| X[0]=con[0]/cof[0][0]; | |
| for(i=0; i<m; i++) delete [] cof[i]; | |
| return ; | |
| } | |
| /************** RMQ *******************/ | |
| http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor | |
| const int MAXN = 50005; | |
| const int LOGMAXN = 16; | |
| int M[MAXN][LOGMAXN]; | |
| int A[MAXN]; | |
| int N; | |
| void pre_process() | |
| { | |
| int i, j; | |
| //initialize M for the intervals with length 1 | |
| for (i = 0; i < N; i++) | |
| M[i][0] = i; | |
| //compute values from smaller to bigger intervals | |
| for (j = 1; (1 << j) <= N; j++) | |
| for (i = 0; i + (1 << (j - 1)) < N; i++) { | |
| if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]]) | |
| M[i][j] = M[i][j - 1]; | |
| else | |
| M[i][j] = M[i + (1 << (j - 1))][j - 1]; | |
| } | |
| } | |
| // r min q | |
| // return index | |
| int rmq(int i, int j) | |
| { | |
| int k = 0; | |
| while( (1 << k) <= (j-i+1) ) k++; | |
| k --; | |
| if ( A[M[i][k]] <= A[M[j-(1<<k)+1][k]] ) | |
| return M[i][k]; | |
| else | |
| return M[j-(1<<k)+1][k]; | |
| } | |
| /************** 线段树 ****************/ | |
| const int MAXN = 1 << 18; | |
| int a[100001]; | |
| void initialize(int node, int b, int e) | |
| { | |
| if ( b==e) | |
| return; | |
| int mid = (b+e)>>1; | |
| initialize(2*node, b, mid); | |
| initialize(2*node+1, mid+1, e); | |
| // ... | |
| // ... | |
| } | |
| struct S { | |
| int i, j, k; | |
| S(int a, int b, int c) | |
| { | |
| i=a, j=b, k=c; | |
| } | |
| }; | |
| int query(int node, int b, int e, int i, int j) | |
| { | |
| if ( i <= b && e <= j) | |
| return info[node]; | |
| if ( i > e || b > j) | |
| return -1; | |
| int mid = (b+e)>>1; | |
| S le = query(2*node, b, mid, i, j); | |
| S ri = query(2*node+1, mid+1, e, i, j); | |
| if ( le == -1) | |
| return ri; | |
| if ( ri == -1) | |
| return le; | |
| // compute best, return | |
| } | |
| /************ 差分约束系统 *********************/ | |
| /** | |
| * return true for neg loop | |
| */ | |
| bool bellman(int s) | |
| { | |
| memset(d, 0, sizeof(d)); // as if v0 到vi已经松弛了, 就不用添加v0进来 | |
| bool over; | |
| for(int i=0; i <= n; i++) { // attention: 结点数 | |
| over = true; | |
| for(int j=0; j<m; j++) { | |
| if ( d[ E[j].u ] > d[ E[j].v] + E[j].w ) { | |
| over = false; | |
| d[ E[j].u ] = d[ E[j].v] + E[j].w; | |
| } | |
| } | |
| if ( over ) | |
| return true; | |
| } | |
| return false; | |
| } | |
| /***************** 树状数组 *********************/ | |
| // 用于查询连续区间和, 修改某个数值 | |
| // 查询和修改复杂度都为log(n) | |
| int C[MAXX+1]; | |
| int maxX; | |
| inline int lowbit(int x) | |
| { | |
| return (x & -x); // x & (x^(x - 1)) | |
| } | |
| /* | |
| * 把a[k]增加val | |
| */ | |
| inline void add(int k, int val) | |
| { | |
| while (k <= maxX) | |
| { | |
| C[k] += val; | |
| k += lowbit(k); | |
| } | |
| } | |
| /* | |
| * 统计a[1]到a[n]之间的和 | |
| */ | |
| inline int sum(int k) | |
| { | |
| int t = 0; | |
| while (k > 0) | |
| { | |
| t += C[k]; | |
| k -= lowbit(k); | |
| } | |
| return t; | |
| } | |
| /*********** bfs * ***********/ | |
| void bfs(int s) | |
| { | |
| queue<int> Q; | |
| Q.push(s); | |
| visited[s]=true; | |
| while(!Q.empty()) { | |
| t=Q.front(); | |
| Q.pop(); | |
| if ( t == target ) | |
| // got it | |
| int a=opA(t); | |
| if(visited[a]==false) { | |
| Q.push(a); | |
| visited[a]=true; | |
| //... | |
| } | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment