http://poj.org/problem?id=1062
枚举层次求最短路，比如酋长等级是5，m是2，那么就要枚举等级在3-5, 4-6, 5-7之间这三种情况的最短路里面的最小值了
以前做过，不过这次做还是一直wa。。。原来是我在dijkstra初始化dist数组的时候出问题了。。弱爆了啊。。wa的真辛苦
poj_1062
#include<cstdio> #include<cstring> const int maxn = 110; int g[maxn][maxn]; int dist[maxn], vis[maxn]; int flag[maxn]; int m, n; int cost[maxn], level[maxn]; const int inf = 100000000; int dijk(){ memset(vis, 0, sizeof vis); for(int i = 1; i <= n; i ++) if(flag[i] && g[1][i] != -1)dist[i] = g[1][i]; else dist[i] = inf; dist[1] = 0; vis[1] = 1; for(int i = 0; i < n - 1; i ++){ int Min = inf, u; for(int j = 1; j <= n; j ++){ if(!vis[j] && flag[j] && dist[j] < Min){ Min = dist[j]; u = j; } } if(Min == inf) break; vis[u] = 1; for(int j = 1;j <= n; j ++){ if(!vis[j] && flag[j] && g[u][j] != -1 && dist[u] + g[u][j] < dist[j]){ dist[j] = dist[u] + g[u][j]; } } } int ans = inf; for(int i = 1; i <= n; i ++){ dist[i] += cost[i]; if(dist[i] < ans) ans = dist[i]; } //printf("dijk: %d\n", ans); return ans; } int main(){ while(~scanf("%d%d", &m, &n)){ memset(g, -1, sizeof g); for(int i = 1; i <= n; i ++){ int p, l, x; scanf("%d%d%d", &p, &l, &x); cost[i] = p, level[i] = l; while(x --){ int t, v; scanf("%d%d", &t, &v); g[i][t] = v; } } int ans = inf; for(int i = 0; i <= m; i ++){ memset(flag, 0, sizeof flag); for(int j = 1; j <= n; j ++) if(level[j] >= level[1] - m + i && level[j] <= level[1] + i) flag[j] = 1; int c = dijk(); if(c < ans ) ans = c; } printf("%d\n", ans); } return 0; }
http://poj.org/problem?id=1087
给你一些现有的插座，然后给一些电器，这些电器必须用对应的插座，然后给一些转换器，可以把一些插座转换成另外的插座
很明显的二分匹配，不过当时做的时候，一直在建图那一块出错。。。。最后的图是用floyd传递闭包之后再建图，很麻烦= =
当然，这次也练习了下用网络流来解匹配的问题了，还是很好理解的
poj_1087_maxmatch
#include<cstdio> #include<cstring> const int maxn = 610; const int inf = 10000000; int g[maxn][maxn], gg[maxn][maxn]; int link[maxn], vis[maxn]; char str[maxn][30], plug[maxn][30]; int cnt; int n, m, k; int find(char s[]){ int i; for(i = 0; i < cnt; i ++){ if(strcmp(s, str[i]) == 0) return i; } return i; } void init(){ cnt = 0; memset(g, 0, sizeof g); memset(gg, 0, sizeof gg); } void build(){ for(int i = 0; i < cnt; i ++){ for(int j = 0; j < cnt; j ++){ for(int k = 0; k < cnt; k ++){ //if(i == j || i == k) continue; if(g[j][i] && g[i][k]) g[j][k] = 1; } } } memset(gg, 0, sizeof gg); for(int i = 0; i < m; i ++){ int pos = find(plug[i]); gg[i][pos] = 1; for(int j = 0; j < n; j ++){ if(g[pos][j]) gg[i][j] = 1; } } } int dfs(int u){ for(int i = 0; i < n; i ++){ if(!vis[i] && gg[u][i]){ vis[i] = 1; if(link[i] == -1 || dfs(link[i])){ link[i] = u; return 1; } } } return 0; } int maxmatch(){ memset(link, -1, sizeof link); int ans = 0; for(int i = 0; i <m; i ++){ memset(vis, 0, sizeof vis); if(dfs(i)) ans ++; //printf("ans: %d\n", ans); } return ans; } int main(){ scanf("%d", &n); init(); for(int i = 0; i < n;i ++){ char s[30]; scanf("%s", s); strcpy(str[cnt], s); cnt++; } scanf("%d", &m); for(int i = 0; i < m;i ++){ char s[30], ss[30]; scanf("%s%s", s, ss); strcpy(plug[i], ss); int tmp = find(ss); if(tmp == cnt){ strcpy(str[cnt], ss); cnt ++; } //g[i][tmp] = 1; //gg[i][tmp] = 1; } scanf("%d", &k); for(int i = 0; i < k; i ++){ char s[30], ss[30]; scanf("%s%s", s, ss); int a = find(s); if(a == cnt){ strcpy(str[cnt], s); cnt ++; //a = cnt - 1; } int b = find(ss); if(b == cnt){ strcpy(str[cnt], ss); cnt ++; //b = cnt - 1; } g[a][b] = 1; } build(); printf("%d\n", m - maxmatch()); return 0; }
poj_1087_maxflow
#include<cstdio> #include<cstring> #include<iostream> #include<map> using namespace std; map <string, int> v; const int maxn(600); const int inf(10000000); int n, m, k; int s = 0, t = 1, cnt = 2; int c[maxn][maxn]; int level[maxn], gap[maxn]; int cur[maxn], pre[maxn]; int sap(){ int maxflow = 0; memset(level, 0, sizeof level); memset(gap, 0, sizeof gap); memset(cur, 0, sizeof cur); gap[s] = cnt; int aug = inf; int u = pre[s] = s, v; while(level[s] < cnt){ for(v = cur[u]; v < cnt; v ++){ if(c[u][v] && level[u] == level[v] + 1) break; } //puts("--"); if(v < cnt){ // puts("asdf"); pre[v] = u; if(aug > c[u][v]) aug = c[u][v]; u = cur[u] = v; if(u == t){ maxflow += aug; for(v = t; v != s; v = pre[v]){ c[pre[v]][v] -= aug; c[v][pre[v]] += aug; } aug = inf, u = s; } }else{ int min_label = cnt; for(v = 0; v < cnt; v ++){ if(c[u][v] && min_label > level[v]){ min_label = level[v]; cur[u] = v; } } if(--gap[level[u]] == 0)return maxflow; level[u] = min_label + 1; gap[level[u]] ++; u = pre[u]; } } return maxflow; } int main(){ scanf("%d", &n); for(int i = 0; i < n; i ++){ string s; cin>>s; v[s] = cnt; c[cnt++][t] = 1; } scanf("%d", &m); for(int i = 0; i < m; i ++){ string s1, s2; cin>>s1>>s2; v[s1] = cnt; c[s][cnt++] = 1; if(!v.count(s2)) v[s2] = cnt ++; c[v[s1]][v[s2]] = 1; } scanf("%d", &k); for(int i = 0; i < k; i ++){ string s1, s2; cin>>s1>>s2; if(!v.count(s1)) v[s1] = cnt ++; if(!v.count(s2)) v[s2] = cnt ++; c[v[s1]][v[s2]] = inf; } printf("%d\n", m - sap()); return 0; }
http://poj.org/problem?id=1094
拓扑排序，题意有个trick啊。。。。我一直坑在这了。。还是看着解题报告想了好久才明白的
其实是我没理解清，题目要求必须给出一个升序的，如果topsort的时候，有两个点可以选择，即这两个点不能确定拓扑关系。。就不能说确定的升序了。。。
当然，这题也有用floyd做的。。我没研究。。
poj_1094
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int g[30][30]; int ind[30]; int vis[30]; char ans[30]; int n, m; int sta[30]; int pos; int topsort(){ pos = 0; // int top = -1; int ind1[30]; for(int i = 0; i <= 26; i ++) ind1[i] = ind[i]; // for(int i = 0; i < n; i ++){ // if(vis[i] == 0) continue; // if(ind1[i] == 0){ //ind1[i] = top; // top = i; // } // } int flag = 0; for(int i = 0; i < n; i ++){ // if(vis[i] == 0) continue; // if(top == -1) return -1; int u = 0; int num = 0; for(int j = 0; j < n; j ++){ if(ind1[j] == 0){ u = j; num ++; } } if(num == 0)return -1; if(num > 1)//return -2; flag = 1; //top = ind1[top]; ind1[u] = -1; // sta[pos++] = u; pos += sprintf(ans + pos, "%c", u + 65); for(int j = 0; j < n; j ++){ // if(vis[j] == 0) continue; if(g[u][j]){ // if(--ind1[j] == 0){ // ind1[j] = top; // top = j; ind1[j] --; // } } } } if(flag) return -2; ans[pos] = '\0'; //sort(ans, ans + pos); return pos; } int main(){ while(scanf("%d%d", &n, &m), n || m){ memset(g, 0, sizeof g); memset(ind, 0, sizeof ind); memset(vis, 0, sizeof vis); int f = 0; for(int i = 1; i <= m; i ++){ char s[10];; scanf("%s", s); int v = s[0] - 65, u = s[2] - 65; if(g[v][u])continue; g[v][u] = 1; ind[u] ++; vis[u] = vis[v] = 1; if(f) continue; int t = topsort(); if(t == -1){ printf("Inconsistency found after %d relations.\n", i); f = 1; }else if(t == n){ printf("Sorted sequence determined after %d relations: %s.\n", i,ans); // for(int j = 0; j < pos; j ++)putchar(sta[j]+65); // puts("."); f = 1; } } if(!f)puts("Sorted sequence cannot be determined."); } return 0; }
http://poj.org/problem?id=1112
这是最后完成的一题。。。看着解题报告抄的。。。边抄边理解啊T_T我感觉我还是没理解透这题。。
先求补图，然后求强连通，然后DP。。
贴个代码吧。。
poj_1112
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int maxn(128); bool map[maxn][maxn], tmp[maxn][maxn], vis[maxn], f[maxn][maxn]; int c[maxn], a[maxn], b[maxn], st[maxn], l[maxn][maxn]; int mind = maxn, s = 0, rt[maxn]; int k1[maxn], k2[maxn]; int lk1 = 0, lk2 = 0; int n, x, cnt; void init(){ scanf("%d", &n); memset(tmp, false, sizeof tmp); for(int i = 1; i <= n; i ++){ scanf("%d", &x); while(x != 0){ tmp[i][x] = true; scanf("%d", &x); } } memset(map, false, sizeof map); for(int i = 1; i <= n; i ++){ for(int j = i + 1; j <= n; j ++){ if(!(tmp[i][j] && tmp[j][i])){ map[i][j] = map[j][i] = true; } } } } bool fill(int v, int color){ c[v] = color; vis[v] = true; for(int i = 1; i <= n; i ++){ if(map[v][i]){ if(c[i] == color) return false; else if(c[i] == 0){ if(!fill(i, -color)) return false; } } } return true; } bool make(){ memset(vis, false, sizeof vis); memset(c, 0, sizeof c); memset(a, 0, sizeof a); memset(b, 0, sizeof b); cnt = 0; for(int i = 1; i <= n; i ++){ if(!vis[i]){ if(!fill(i, i)) return false; cnt ++; for(int j = 1; j <= n; j ++){ a[cnt] += (c[j] == i); b[cnt] += (c[j] == -i); } st[cnt] = i; } } return true; } int abs(int a){ return a > 0 ? a : -a; } void dp(){ memset(f, false, sizeof f); f[0][0] = 1; for(int i = 1; i <= cnt; i ++){ for(int j = n; j >= 0; j --){ for(int k = n; k >= 0; k --){ if(f[j][k]) continue; if(j >= a[i] && k >= b[i]){ if(f[j - a[i]][k - b[i]]){ f[j][k] = true; l[j][k] = i; } } if(j >= b[i] && k >= a[i]){ if(f[j - b[i]][k - a[i]]){ f[j][k] = true; l[j][k] = -i; } } } } } } void print(){ memset(k1, 0, sizeof k1); memset(k2, 0, sizeof k2); lk1 = 0, lk2 = 0; for(int i = 1; i <= s; i ++){ for(int j = 1; j <= n; j ++){ if(rt[i] > 0){ if(c[j] == st[rt[i]]) k1[++lk1] = j; if(c[j] == -st[rt[i]])k2[++lk2] = j; }else{ if(c[j] == -st[-rt[i]])k1[++lk1] = j; if(c[j] == st[-rt[i]]) k2[++lk2] = j; } } } for(int i = 1; i < lk1; i ++){ for(int j = i + 1; j <= lk1; j ++) if(k1[i] > k1[j]) swap(k1[i], k1[j]); } for(int i = 1; i < lk2; i ++){ for(int j = i + 1; j <= lk2; j ++) if(k2[i] > k2[j]) swap(k2[i], k2[j]); } printf("%d", lk1); for(int i = 1; i <= lk1; i ++) printf(" %d", k1[i]); puts(""); printf("%d", lk2); for(int i = 1; i <= lk2; i ++) printf(" %d", k2[i]); puts(""); } void solve(){ dp(); mind = maxn; s = 0; memset(rt, 0, sizeof rt); for(int i = 0; i <= n; i ++){ for(int j = 0; j <= n; j ++) if(f[i][j] && (i+j == n)) mind = min(mind, abs(i-j)); } for(int i = 0; i <= n; i ++) for(int j = 0; j <= n; j ++) if(f[i][j] && (i+j == n) && abs(i-j) == mind){ int x = i, y = j, dx, dy; while(x + y){ rt[++s] = l[x][y]; if(l[x][y] > 0){ dx = a[l[x][y]]; dy = b[l[x][y]]; }else{ dx = b[abs(l[x][y])]; dy = a[abs(l[x][y])]; } x -= dx; y -= dy; } print(); return; } } int main(){ init(); if(!make()) puts("No solution"); else solve(); return 0; }
http://poj.org/problem?id=1125
这题明显的题目理解难度大于题目难度啊。。
不过这题好早做过。。。直接贴的代码。。太恶心
poj_1125
#include<cstdio> #include<cstring> int g[110][110]; const int inf = 10000000; int main(){ int n; while(scanf("%d", &n), n){ for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n ;j ++){ if(i == j) g[i][j] = 0; else g[i][j] = inf; } } for(int i = 1; i <= n; i ++){ int num; scanf("%d", &num); while(num --){ int id, time; scanf("%d%d", &id, &time); g[i][id] = time; } } for(int k = 1; k <= n; k ++){ for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++){ if(k == i || k == j) continue; if(g[i][k] + g[k][j] < g[i][j]) g[i][j] = g[i][k] + g[k][j]; } } } int min = inf, max; int id; for(int i = 1; i <= n; i ++){ max = 0; for(int j = 1;j <= n; j ++){ if(max < g[i][j]) max = g[i][j]; } if(max < min){ id = i; min = max; } } if(min == inf) puts("disjoint");else printf("%d %d\n", id, min); } return 0; }
http://poj.org/problem?id=1135
就是骨牌，倒，然后求最后倒的地方和时间
最短路= =畸形的
如果是一个点的话就输出位置和时间了，如果不是，那么就在一条边上了
现在的问题是，怎么样才能确定在这条边上呢？
好吧，我也不知道，没有想出来，看着书上的做法的，很好啊！
poj_1135
#include<cstdio> #include<cstring> const int maxn(555); const int inf(100000000); int n, m; int g[maxn][maxn]; int dist[maxn], vis[maxn]; void solve(int z){ memset(vis, 0, sizeof vis); for(int i = 1; i <= n; i ++) dist[i] = g[1][i]; vis[1] = 1; dist[1] = 0; for(int i = 1; i < n; i ++){ int min = inf, u; for(int j = 1; j <= n; j ++){ if(!vis[j] && dist[j] < min){ min = dist[j]; u = j; } } if(min == inf) break; vis[u] = 1; for(int j = 1; j <= n; j ++){ if(!vis[j] && g[u][j] < inf && dist[u] + g[u][j] < dist[j]) dist[j] = dist[u] + g[u][j]; } } int pos, pos1, pos2; double time1 = -1, time2 = -1; for(int i = 1; i <= n; i ++){ if(time1 < dist[i] + 0.0){ time1 = dist[i] + 0.0; pos = i; } } for(int j = 1; j <= n; j ++){ for(int i = 1; i <= n; i ++){ double t = (dist[i] + dist[j] + g[j][i]) / 2.0; if(g[j][i] < inf && time2 < t){ time2 = t; pos1 = j; pos2 = i; } } } printf("System #%d\n", z); if(time2 > time1) printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n\n", time2, pos1, pos2); else printf("The last domino falls after %.1f seconds, at key domino %d.\n\n", time1, pos); } int main(){ int z = 1; while(scanf("%d%d", &n, &m), n||m){ for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) g[i][j] = inf; for(int i = 1; i <= m; i ++){ int u, v, w; scanf("%d%d%d", &u, &v, &w); g[u][v] = g[v][u] = w; } solve(z++); } return 0; }
http://poj.org/problem?id=1149
好经典的最大流啊，第一次学网络流的时候就是做的这题
其实这题来学网络流还是挺好的，不过这题的难点是在建图啊。。。。。。。。。。。。。死活也建不出来。
最大流我只会sap
poj_1149
#include<cstdio> #include<cstring> const int inf = 100000000; const int maxn = 110; int s, t; int level[maxn], gap[maxn]; int cur[maxn], pre[maxn]; int c[maxn][maxn]; int m, n; void input(){ int last[maxn*10]; memset(last, 0, sizeof last); s = 0, t = n + 1; int tmp[maxn * 10]; memset(c, 0, sizeof c); for(int i = 1; i <= m; i ++) scanf("%d", tmp + i); for(int i = 1; i <= n; i ++){ int num; scanf("%d", &num); while(num --){ int k; scanf("%d", &k); if(last[k] == 0) c[s][i] += tmp[k]; else c[ last[k] ][i] = inf; last[k] = i; } scanf("%d", &num); c[i][t] = num; } n += 2; } int sap(){ memset(level, 0, sizeof level); memset(gap, 0, sizeof gap); memset(cur, 0, sizeof cur); int u = pre[s] = s; int aug = inf; gap[s] = n; int v; int flow = 0; while(level[s] < n){ for(v = cur[u]; v < n; v ++){ if(c[u][v] > 0 && level[u] == level[v] + 1){ break; } } if(v < n){ pre[v] = u; if(aug > c[u][v]) aug = c[u][v]; u = cur[u] = v; if(u == t){ flow += aug; for(v = t; v != s; v = pre[v]){ if(c[pre[v]][v] != inf) c[pre[v]][v] -= aug; if(c[v][pre[v]] != inf) c[v][pre[v]] += aug; } aug = inf, u = s; } }else{ int min_label = t; for(v = 0; v < n; v ++){ if(c[u][v] > 0 && min_label > level[v]){ cur[u] = v; min_label = level[v]; } } if(--gap[level[u]] == 0) return flow; level[u] = min_label + 1; gap[level[u]] ++; u = pre[u]; } } return flow; } int main(){ while(~scanf("%d%d", &m, &n)){ input(); printf("%d\n", sap()); } return 0; }
http://poj.org/problem?id=1161
唉。。这题是我见过的最神奇的题了
主要难点还是解题思路以及建图。。。。。。。。。。Orz太神奇
以环为点建图！！！
图构造好了然后就是floyd枚举最小值了
poj_1161
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn(300); const int inf(100000000); int n, m; struct Person{ int reg[maxn]; int num; int id; }p[maxn]; int reg[maxn][maxn]; int g[maxn][maxn]; int reg_num[maxn]; int is_ok(int u, int v){ for(int i = 1; i <= reg_num[u]; i ++){ for(int j = 1; j <= reg_num[v]; j ++){ if(reg[u][i] == reg[v][j]){ if(reg[u][i-1] == reg[v][j-1]|| reg[u][i-1] == reg[v][j+1]|| reg[u][i+1] == reg[v][j+1]|| reg[u][i+1] == reg[v][j-1]) return 1; } } } return 0; } void floyd(){ for(int k = 1; k <= m; k ++){ for(int i = 1; i <= m; i ++){ for(int j = 1; j <= m; j ++){ //if(k == i || k == j) continue; // printf("%d ", g[i][j]); g[i][j] = g[j][i] = min(g[i][j], g[i][k] + g[k][j]); } // puts(""); } // puts("\n\n"); } /* for(int i = 1; i <= m; i ++){ for(int j = 1; j < m; j ++) printf("%d ", g[i][j]); printf("%d\n", g[i][m]); }*/ } int num; int find(int u){ int sum = 0; for(int i = 0; i < num; i ++){ int tmp = inf; for(int j = 0; j < p[i].num; j ++) tmp = min(tmp, g[p[i].reg[j]][u]); sum += tmp; } // printf("-- %d\n", sum); return sum; } int main(){ while(~scanf("%d%d", &m, &n)){ scanf("%d", &num); for(int i = 0; i < num; i ++){ int t; scanf("%d", &t); p[i].id = t; p[i].num = 0; } for(int i = 1; i <= m; i ++){ scanf("%d", reg_num + i); for(int j = 1; j <= reg_num[i]; j ++){ int t; scanf("%d", &t); reg[i][j] = t; for(int k = 0; k < num; k ++) if(t == p[k].id) p[k].reg[p[k].num ++] = i; } reg[i][0] = reg[i][reg_num[i]]; reg[i][reg_num[i]+1] = reg[i][1]; } for(int i = 1; i <= m; i ++){ for(int j = 1; j <= m; j ++){ if(i == j){ g[i][j] = g[j][i] = 0; continue; } if(is_ok(i, j)) g[i][j] = g[j][i] = 1; else g[i][j] = g[j][i] = inf; } } floyd(); int ans = inf; for(int i = 1; i <= m; i ++){ int tmp = find(i); ans = min(ans, tmp); } printf("%d\n", ans); } return 0; }
http://poj.org/problem?id=1201
差分约束，我已经放弃这一块内容了。。。感觉找公式太难。。
建图更难
poj_1201
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; const int maxn(55555); const int inf(100000000); struct Edge{ int v, next, w; }e[maxn*10]; int head[maxn], cnt; int l, r; void init(){ cnt = 0; memset(head, -1, sizeof head); l = inf; r = -inf; } void add_Edge(int u, int v, int w){ e[cnt].v = v, e[cnt].w = w, e[cnt].next = head[u]; head[u] = cnt ++; } int dist[maxn], vis[maxn]; int q[maxn*10]; int spfa(){ for(int i = l; i <= r; i ++) dist[i] = -inf; memset(vis, 0, sizeof vis); int qs = 0, qe = 0; q[qe++] = l; vis[l] = 1; dist[l] = 0; while(qs < qe){ int u = q[qs++]; vis[u] = 0; for(int i = head[u]; i+1; i = e[i].next){ int v = e[i].v; if(dist[v] < dist[u] + e[i].w){ dist[v] = dist[u] + e[i].w; if(!vis[v]){ vis[v] = 1; q[qe++] = v; } } } } return dist[r] - dist[l]; } int main(){ while(~scanf("%d", &n)){ init(); for(int i = 0; i < n; i ++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); l = min(l, a); r = max(r, b+1); add_Edge(a, b + 1, c); } for(int i = l; i < r; i ++){ add_Edge(i, i+1, 0); add_Edge(i+1, i, -1); } printf("%d\n", spfa()); } return 0; }
http://poj.org/problem?id=1236
这题很好啊。。强连通的题。。
任务1是求入度为0的点，任务2是求最少加几条边能使这些点变成强连通（我说的点都是指缩点，就是把一个强连通分量看成一个点）
任务1还好，任务2就麻烦了，看了解题报告之后理解了，就是找入度为0和出度为0的点的个数的最大值了
可以看下这个。。。http://www.cnblogs.com/louzhang/archive/2012/08/19/2646316.html
poj_1236
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn(110); int belong[maxn], dfn[maxn], low[maxn], vis[maxn]; struct Edge{ int v, next; }e[maxn*maxn]; int head[maxn], cnt; int in[maxn], out[maxn]; int n; int step, top, color; int stack[maxn]; void init(){ memset(in, 0, sizeof in); memset(out, 0, sizeof out); memset(belong, 0, sizeof belong); memset(dfn, 0, sizeof dfn); memset(low, 0, sizeof low); memset(vis, 0, sizeof vis); memset(head, -1, sizeof head); cnt = 0; step = color = top = 0; } void add_Edge(int u, int v){ e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt ++; } void targan(int u){ low[u] = dfn[u] = ++ step; vis[u] = 1; stack[top++] = u; for(int i = head[u]; i+1; i = e[i].next){ int v = e[i].v; if(!dfn[v]){ targan(v); if(low[u] > low[v]) low[u] = low[v]; }else if(vis[v] && low[u] > dfn[v]) low[u] = dfn[v]; } ///puts("asdfasdf"); if(low[u] == dfn[u]){ color++; int s; do{ s = stack[--top]; vis[s] = 0; belong[s] = color; //puts("----"); }while(u != s); } } void solve(){ for(int i = 1; i <= n; i ++) if(!dfn[i]) targan(i); if(color == 1){ puts("1\n0"); return; } //puts("++++"); int ans1 = 0, ans2 = 0; for(int i = 1; i <= n; i ++){ for(int j = head[i]; j+1; j = e[j].next){ int v = e[j].v; if(belong[i] != belong[v]){ in[belong[v]] ++; out[belong[i]] ++; } } } //puts("00000"); for(int i = 1; i <= color; i ++){ if(in[i] == 0) ans1++; if(out[i] == 0) ans2 ++; } printf("%d\n%d\n", ans1, max(ans1, ans2)); } int main(){ while(~scanf("%d", &n)){ int v; init(); for(int i = 1; i <= n; i ++){ while(scanf("%d", &v), v){ add_Edge(i, v); } } solve(); } return 0; }
http://poj.org/problem?id=1251
MST乱搞即可
poj_1251
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn(1111); const int inf(100000000); struct Edge{ int u, v, next, w; }e[maxn]; int head[maxn], cnt; int n; int dist[maxn], vis[maxn]; void init(){ memset(head, -1, sizeof head); cnt = 0; } void add_Edge(int u, int v, int w){ e[cnt].u = u, e[cnt].v = v, e[cnt].w = w, e[cnt].next = head[u]; head[u] = cnt ++; e[cnt].u = v, e[cnt].v = u, e[cnt].w = w, e[cnt].next = head[v]; head[v] = cnt ++; } void prim(){ for(int i = 0; i < n; i ++) dist[i] = inf; memset(vis, 0, sizeof vis); int ans = 0; dist[0] = 0; for(int i = 0; i < n; i ++){ int Min = inf, u; for(int j = 0; j < n; j ++){ if(!vis[j] && dist[j] < Min){ Min = dist[j]; u = j; } } if(Min == inf) break; vis[u] = 1; ans += Min; for(int j = head[u]; j + 1; j = e[j].next){ int v = e[j].v; if(!vis[v] && e[j].w < dist[v]) dist[v] = e[j].w; } } printf("%d\n", ans); } int main(){ while(scanf("%d", &n), n){ init(); for(int i = 1; i < n; i ++){ char s[3]; int num; scanf("%s%d", s, &num); while(num --){ char op[3]; int w; scanf("%s%d", op, &w); add_Edge(s[0] - 65, op[0] - 65, w); } } prim(); } return 0; }
http://poj.org/problem?id=1273
最大流
poj_1273
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int s, t; const int inf = 2000000000; const int maxn = 300; int level[maxn], gap[maxn]; int c[maxn][maxn], cur[maxn], pre[maxn]; int n, m; int sap(){ memset(gap, 0, sizeof gap); memset(level, 0, sizeof level); memset(cur, 0, sizeof cur); int u = pre[s] = s, v; gap[s] = n; int aug = inf; int flow = 0; while(level[s] < n){ for(v = cur[u]; v <= n; v ++){ if(c[u][v] && level[u] == level[v] + 1) break; } if(v <= n){ pre[v] = u; aug = min(aug, c[u][v]); u = cur[u] = v; if(u == t){ flow += aug; for(v = t; v != s; v = pre[v]){ c[pre[v]][v] -= aug; c[v][pre[v]] += aug; } aug = inf, u = s; } }else{ if(--gap[level[u]] == 0) return flow; int min_label = n; for(v = 1; v <= n; v ++){ if(c[u][v] && min_label > level[v]){ cur[u] = v; min_label = level[v]; } } level[u] = min_label + 1; gap[level[u]]++; u = pre[u]; } } return flow; } int main(){ while(~scanf("%d%d", &m, &n)){ memset(c, 0, sizeof c); while(m --){ int u, v, w; scanf("%d%d%d", &u, &v, &w); c[u][v] += w; } s = 1, t = n; printf("%d\n", sap()); } return 0; }
http://poj.org/problem?id=1274
裸的二分匹配了。。
poj_1274
#include<cstdio> #include<cstring> const int maxn = 222; int link[maxn], vis[maxn]; int g[maxn][maxn]; int n, m; int dfs(int u){ for(int v = 1; v <= m; v ++){ if(g[u][v] && !vis[v]){ vis[v] = 1; if(link[v] == -1 || dfs(link[v])){ link[v] = u; return 1; } } } return 0; } int max_match(){ memset(link, -1, sizeof link); int ans = 0; for(int i = 1; i <= n; i ++){ memset(vis, 0, sizeof vis); if(dfs(i)) ans++; } return ans; } int main(){ while(~scanf("%d%d", &n, &m)){ memset(g, 0, sizeof g); for(int i = 1; i <= n; i ++){ int num; scanf("%d", &num); while(num --){ int t; scanf("%d", &t); g[i][t] = 1; } } printf("%d\n", max_match()); } return 0; }
http://poj.org/problem?id=1325
二分匹配，就是机器调换来调换去。。。
poj_1325
#include<cstdio> #include<cstring> const int maxn(111); int link[maxn], vis[maxn], g[maxn][maxn]; int n, m, k; int dfs(int u){ for(int i = 1; i < m; i ++){ if(g[u][i] && !vis[i]){ vis[i] = 1; if(link[i] == -1 || dfs(link[i])){ link[i] = u; return 1; } } } return 0; } int max_match(){ memset(link, -1, sizeof link); int ans = 0; for(int i = 1; i < n; i ++){ memset(vis, 0, sizeof vis); ans += dfs(i); //if(dfs(i)) ans ++; } return ans; } int main(){ while(scanf("%d", &n), n){ scanf("%d%d", &m, &k); memset(g, 0, sizeof g); while(k --){ int a, u, v; scanf("%d%d%d", &a, &u, &v); //if(u * v == 0) continue; g[u][v] = 1; } printf("%d\n", max_match()); } return 0; }
http://poj.org/problem?id=1422
最小路径覆盖 = 点数 - 匹配数
poj_1422
#include<cstdio> #include<cstring> const int maxn(1111); int link[maxn], vis[maxn], g[maxn][maxn]; int n, m, k; int dfs(int u){ for(int i = 1; i <= n; i ++){ if(g[u][i] && !vis[i]){ vis[i] = 1; if(link[i] == -1 || dfs(link[i])){ link[i] = u; return 1; } } } return 0; } int max_match(){ memset(link, -1, sizeof link); int ans = 0; for(int i = 1; i <= n; i ++){ memset(vis, 0, sizeof vis); ans += dfs(i); //if(dfs(i)) ans ++; } return ans; } int main(){ int tcase; scanf("%d", &tcase); while(tcase --){ memset(g, 0, sizeof g); scanf("%d%d", &n, &m); while(m --){ int u, v; scanf("%d%d", &u, &v); //if(u * v == 0) continue; g[u][v] = 1; } printf("%d\n", n - max_match()); } return 0; }
http://poj.org/problem?id=1459
唉。。第一个会的最大流
poj_1459
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 111; const int inf = 100000000; int n, np, nc, m; int gap[maxn], level[maxn]; int cur[maxn], pre[maxn]; int s, t; int c[maxn][maxn]; int sap(){ memset(gap, 0, sizeof gap); memset(cur, 0, sizeof cur); memset(level, 0, sizeof level); int u = pre[s] = s, v; int flow = 0; gap[s] = n; int aug = inf; while(level[s] < n){ for(v = cur[u]; v < n; v ++){ if(c[u][v] && level[u] == level[v] + 1) break; } if(v < n){ pre[v] = u; aug = min(aug, c[u][v]); u = cur[u] = v; if(u == t){ flow += aug; for(v = t; v != s; v = pre[v]){ c[pre[v]][v] -= aug; c[v][pre[v]] += aug; } aug = inf, u = s; } }else{ if(--gap[level[u]] == 0) return flow; int min_label = n; for(v = 0; v < n; v ++){ if(c[u][v] && min_label > level[v]){ min_label = level[v]; cur[u] = v; } } level[u] = min_label + 1; gap[level[u]] ++; u = pre[u]; } } return flow; } int main(){ while(~scanf("%d%d%d%d", &n, &np, &nc, &m)){ s = n, t = n + 1, n += 2; memset(c, 0, sizeof c); while(m--){ int u, v, w; scanf(" (%d,%d)%d", &u, &v, &w); c[u][v] += w; } while(np --){ int u, w; scanf(" (%d)%d", &u, &w); c[s][u] += w; } while(nc --){ int v, w; scanf(" (%d)%d", &v, &w); c[v][t] += w; } printf("%d\n", sap()); } return 0; }
http://poj.org/problem?id=1466
最大独立集 = 点数 - 匹配数
不过这题因为双向边，可能匹配两次，所以匹配数得除以2
poj_1466
#include<cstdio> #include<cstring> const int maxn(1111); int link[maxn], vis[maxn]; int n; int g[maxn][maxn]; int dfs(int u){ for(int i = 0; i < n; i ++){ if(g[u][i] && !vis[i]){ vis[i] = 1; if(link[i] == -1 || dfs(link[i])){ link[i] = u; return 1; } } } return 0; } int max_match(){ int ans = 0; memset(link, -1, sizeof link); for(int i = 0; i < n; i ++){ memset(vis, 0, sizeof vis); ans += dfs(i); } return ans; } int main(){ while(~scanf("%d", &n)){ memset(g, 0, sizeof g); for(int i = 0; i < n; i ++){ int from, num, to; scanf("%d: (%d)", &from, &num); while(num--){ scanf("%d", &to); g[from][to] = 1; } } printf("%d\n", n - max_match() / 2); } return 0; }
http://poj.org/problem?id=1469
二分匹配= =怒了
poj_1469
#include<cstdio> #include<cstring> const int maxn(333); int link[maxn], vis[maxn]; int n, p; int g[maxn][maxn]; int dfs(int u){ for(int i = 1; i <= n; i ++){ if(g[u][i] && !vis[i]){ vis[i] = 1; if(link[i] == -1 || dfs(link[i])){ link[i] = u; return 1; } } } return 0; } int max_match(){ int ans = 0; memset(link, -1, sizeof link); for(int i = 1; i <= p; i ++){ memset(vis, 0, sizeof vis); ans += dfs(i); } return ans; } int main(){ int tcase; scanf("%d", &tcase); while(tcase --){ scanf("%d%d", &p, &n); memset(g, 0, sizeof g); for(int i = 1; i <= p; i ++){ int num; scanf("%d", &num); while(num --){ int t; scanf("%d", &t); g[i][t] = 1; } } if(max_match() == p) puts("YES"); else puts("NO"); } return 0; }
http://poj.org/problem?id=1502
这题看着解题报告 的啊。。。。题目意思看不明白。。明白了就发现是一图论水题了。。
poj_1502
#include<cstdio> #include<cstring> const int maxn(111); const int inf(100000000); int n; int dist[maxn], vis[maxn]; int g[maxn][maxn]; void dijk(){ for(int i = 1; i <= n; i ++) dist[i] = inf; memset(vis, 0, sizeof vis); dist[1] = 0; for(int i = 1; i <= n; i ++){ int min = inf, u; for(int j = 1; j <= n; j ++){ if(!vis[j] && dist[j] < min){ min = dist[j]; u = j; } } if(min == inf) break; vis[u] = 1; for(int j = 1; j <= n; j ++){ if(!vis[j] && g[u][j] < inf && dist[u] + g[u][j] < dist[j]) dist[j] = dist[u] + g[u][j]; } } int ans = -1; for(int i = 1; i <= n; i ++) if(ans < dist[i]) ans = dist[i]; printf("%d\n", ans); } int main(){ while(~scanf("%d", &n)){ for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) if(i == j) g[i][j] = 0;else g[i][j] = inf; for(int i = 2; i <= n; i ++){ for(int j = 1; j < i ; j++){ char op[10]; scanf("%s", op); if(op[0] == 'x'){ g[i][j] = g[j][i] = inf; }else{ int t; sscanf(op, "%d", &t); g[i][j] = g[j][i] = t; } } } dijk(); } return 0; }
http://poj.org/problem?id=1511
最短路，先正向求一次，再反向求一次，加起来即可，这题要用长长整型
poj_1511
#include<cstdio> #include<cstring> #define ll long long const int maxn(1000000+10); const ll inf(1ll<<60); int n, p; struct Edge{ int v, w, next; }e[maxn], ee[maxn]; int head1[maxn], head2[maxn], cnt1, cnt2; void add_Edge(int u, int v, int w){ e[cnt1].v = v, e[cnt1].w = w, e[cnt1].next = head1[u]; head1[u] = cnt1 ++; ee[cnt2].v = u, ee[cnt2].w = w, ee[cnt2].next = head2[v]; head2[v] = cnt2 ++; } void init(){ memset(head1, -1, sizeof head1); memset(head2, -1, sizeof head2); cnt1 = cnt2 = 0; } ll dist1[maxn], dist2[maxn]; int vis[maxn]; int q[maxn]; void spfa1(){ for(int i = 1; i <= n; i ++) dist1[i] = inf; dist1[1] = 0; memset(vis, 0, sizeof vis); vis[1] = 1; int qs = 0, qe = 0; q[qe++] = 1; while(qs < qe){ int u = q[qs++]; vis[u] = 0; for(int i = head1[u]; i + 1; i = e[i].next){ int v = e[i].v; if(dist1[v] > dist1[u] + (ll)e[i].w){ dist1[v] = dist1[u] + (ll)e[i].w; if(!vis[v]){ vis[v] = 1; q[qe++] = v; } } } } } void spfa2(){ for(int i = 1; i <= n; i ++) dist2[i] = inf; dist2[1] = 0; memset(vis, 0, sizeof vis); vis[1] = 1; int qs = 0, qe = 0; q[qe++] = 1; while(qs < qe){ int u = q[qs++]; vis[u] = 0; for(int i = head2[u]; i + 1; i = ee[i].next){ int v = ee[i].v; if(dist2[v] > dist2[u] + (ll)ee[i].w){ dist2[v] = dist2[u] + (ll)ee[i].w; if(!vis[v]){ vis[v] = 1; q[qe++] = v; } } } } } void solve(){ spfa1(); spfa2(); ll ans = 0; for(int i = 2; i <= n; i ++){ ll tmp = dist1[i] + dist2[i]; ans += tmp; } printf("%lld\n", ans); } int main(){ int tcase; scanf("%d", &tcase); while(tcase --){ init(); scanf("%d%d", &n, &p); while(p --){ int u, v, w; scanf("%d%d%d", &u, &v, &w); add_Edge(u, v, w); } solve(); } return 0; }
http://poj.org/problem?id=1637
混合图的欧拉回路问题。。
可以看下这个 http://www.cnblogs.com/louzhang/archive/2012/08/20/2647784.html
poj_1637
#include<cstdio> #include<cstring> const int maxn(222); const int inf(100000000); int level[maxn], gap[maxn]; int cur[maxn], pre[maxn]; struct Edge{ int v, to, w, next; }e[maxn*10]; int head[maxn], cnt; int s, t; void add_Edge(int u, int v, int w){ e[cnt].v = v, e[cnt].w = w, e[cnt].next = head[u]; head[u] = cnt ++; e[cnt].v = u, e[cnt].w = 0, e[cnt].next = head[v]; head[v] = cnt ++; } int n, m; int in[maxn], out[maxn]; void init(){ memset(head, -1, sizeof head); cnt = 0; memset(in, 0, sizeof in); memset(out, 0, sizeof out); } int f(int a, int b){ return a > b ? a - b : b - a; } int sap(){ memset(gap, 0, sizeof gap); memset(level, 0, sizeof level); int u = pre[s] = s, v; int aug = inf; int flow = 0; gap[s] = n; for(int i = 0; i < n; i ++) cur[i] = head[i]; while(level[s] < n){ bool flag = false; for(int &i = cur[u]; i + 1; i = e[i].next){ v = e[i].v; if(e[i].w && level[u] == level[v] + 1){ flag = true; if(aug > e[i].w) aug = e[i].w; pre[v] = u; u = v; if(u == t){ flow += aug; while(u != s){ u = pre[u]; e[cur[u]].w -= aug; e[cur[u]^1].w += aug; } aug = inf; } break; } } if(flag) continue; if(--gap[level[u]] == 0) return flow; int min_label = n; for(int i = head[u]; i + 1; i = e[i].next){ v = e[i].v; if(level[v] < min_label && e[i].w){ cur[u] = i; min_label = level[v]; } } level[u] = min_label + 1; gap[level[u]] ++; u = pre[u]; } return flow; } int main(){ int tcase; scanf("%d", &tcase); while(tcase --){ init(); scanf("%d%d", &n, &m); int u, v, w; while(m --){ scanf("%d%d%d", &u, &v, &w); out[u] ++; in[v] ++; if(!w) add_Edge(u, v, 1); } int flag = 0; for(int i = 1; i <= n; i ++){ if(f(in[i], out[i]) & 1){ flag = 1; break; } } if(flag){ puts("impossible"); continue; } s = 0, t = n + 1; n += 2; int sum = 0; for(int i = 1; i <= n; i ++){ int x = out[i] - in[i]; if(x > 0){ sum += x/2; add_Edge(s, i, x/2); }else add_Edge(i, t, -x/2); } //puts("asfs"); if(sap() == sum) puts("possible"); else puts("impossible"); } return 0; }
http://poj.org/problem?id=1716
跟1201一样的差分约束问题。。
poj_1716
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; const int maxn(55555); const int inf(100000000); struct Edge{ int v, next, w; }e[maxn*10]; int head[maxn], cnt; int l, r; void init(){ cnt = 0; memset(head, -1, sizeof head); l = inf; r = -inf; } void add_Edge(int u, int v, int w){ e[cnt].v = v, e[cnt].w = w, e[cnt].next = head[u]; head[u] = cnt ++; } int dist[maxn], vis[maxn]; int q[maxn*10]; int spfa(){ for(int i = l; i <= r; i ++) dist[i] = -inf; memset(vis, 0, sizeof vis); int qs = 0, qe = 0; q[qe++] = l; vis[l] = 1; dist[l] = 0; while(qs < qe){ int u = q[qs++]; vis[u] = 0; for(int i = head[u]; i+1; i = e[i].next){ int v = e[i].v; if(dist[v] < dist[u] + e[i].w){ dist[v] = dist[u] + e[i].w; if(!vis[v]){ vis[v] = 1; q[qe++] = v; } } } } return dist[r] - dist[l]; } int main(){ while(~scanf("%d", &n)){ init(); for(int i = 0; i < n; i ++){ int a, b, c; scanf("%d%d", &a, &b); l = min(l, a); r = max(r, b+1); add_Edge(a, b + 1, 2); } l = 0; for(int i = l; i <= r; i ++){ add_Edge(i, i+1, 0); add_Edge(i+1, i, -1); } printf("%d\n", spfa()); } return 0; }
http://poj.org/problem?id=1724
poj_1724
#include<cstdio> #include<cstring> #include<queue> using namespace std; int k, n, r; const int inf(100000000); const int maxn(111); struct Edge{ int v, w, c, next; }e[maxn*maxn*10]; int head[maxn], cnt; int dist[maxn]; void add_Edge(int u, int v, int w, int c){ e[cnt].v = v, e[cnt].w = w, e[cnt].c = c, e[cnt].next = head[u]; head[u] = cnt ++; } void init(){ memset(head, -1, sizeof head); cnt = 0; } struct Point{ int u, dist, c; friend bool operator < (const Point &a, const Point &b){ return a.dist > b.dist; } }; int dijk(Point s){ priority_queue < Point > q; q.push(s); while(!q.empty()){ Point tmp = q.top(); q.pop(); if(tmp.u == n) return tmp.dist; for(int i = head[tmp.u]; i + 1; i = e[i].next){ if(e[i].c + tmp.c <= k){ Point now; now.u = e[i].v; now.c = e[i].c + tmp.c; now.dist = e[i].w + tmp.dist; q.push(now); } } } return -1; } int main(){ while(~scanf("%d%d%d", &k, &n, &r)){ init(); while(r--){ int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c); add_Edge(u, v, w, c); } Point s; s.u = 1, s.c = 0, s.dist = 0; printf("%d\n", dijk(s)); } return 0; }
有限制的最短路，用dijkstra，在更新的时候，只要cost满足就加入到队列，然后把dist最小的先拿出来，用到了优先队列（堆实现也可以，其实一样）
poj_1724
#include<cstdio> #include<cstring> #include<queue> using namespace std; int k, n, r; const int inf(100000000); const int maxn(111); struct Edge{ int v, w, c, next; }e[maxn*maxn*10]; int head[maxn], cnt; int dist[maxn]; void add_Edge(int u, int v, int w, int c){ e[cnt].v = v, e[cnt].w = w, e[cnt].c = c, e[cnt].next = head[u]; head[u] = cnt ++; } void init(){ memset(head, -1, sizeof head); cnt = 0; } struct Point{ int u, dist, c; friend bool operator < (const Point &a, const Point &b){ return a.dist > b.dist; } }; int dijk(Point s){ priority_queue < Point > q; q.push(s); while(!q.empty()){ Point tmp = q.top(); q.pop(); if(tmp.u == n) return tmp.dist; for(int i = head[tmp.u]; i + 1; i = e[i].next){ if(e[i].c + tmp.c <= k){ Point now; now.u = e[i].v; now.c = e[i].c + tmp.c; now.dist = e[i].w + tmp.dist; q.push(now); } } } return -1; } int main(){ while(~scanf("%d%d%d", &k, &n, &r)){ init(); while(r--){ int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c); add_Edge(u, v, w, c); } Point s; s.u = 1, s.c = 0, s.dist = 0; printf("%d\n", dijk(s)); } return 0; }
http://poj.org/problem?id=1780
欧拉路径问题，书上的。。
poj_1780
#include<cstdio> #include<cstring> const int maxn(100000); int list[maxn]; int stack[maxn*10]; char ans[maxn*10]; int s, a; void f(int v, int m){ while(list[v] < 10){ int w = v * 10 + list[v]; list[v] ++; stack[s++] = w; v = w %m; } } int main(){ int n; while(~scanf("%d", &n), n){ if(n == 1) { puts("0123456789"); continue; } s = 0, a = 0; int v = 0; int m = 1; for(int i = 1; i < n; i ++) m *= 10; memset(list, 0, sizeof list); f(v, m); while(s){ v = stack[--s]; ans[a++] = v % 10 + 48; v /= 10; f(v, m); } for(int i = 1; i < n; i ++) printf("0"); while(a) putchar(ans[--a]); puts(""); } return 0; }