程序员人生 网站导航

联合训练图论场

栏目:综合技术时间:2016-06-02 08:35:59

联合训练图论场题解报告

传送门


A.Euler

题意:略

分析:

这题主要是先掌握欧拉通路的概念,然后是如何判断图是不是存在欧拉通路。
欧拉通路:通过图中每条边且只通过1次,并且经过每顶点的通路。
欧拉回路:通过图中每条边且只通过1次,并且经过每顶点的回路。
无向图:
    欧拉通路:连通图+只存在0个或两个度数为奇数的点。
    欧拉回路:连通图+所有节点的度数均为偶数。
有向图:
    欧拉通路:连通图+(所有点的入度=出度 || 出两个点以外其他点的入度=出度,1个点的入度-出度=1,1个点的出度-入度=1)。
ii e[500*500]; int in[510], out[510];//indegree,outdegree int f[510];//判断是不是连通 int find(int x) { return f[x] == -1 ? x : f[x] = find(f[x]); } int main(int argc, const char * argv[]) { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); // clock_t _ = clock(); int t, n, m; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); for (int i = 0;i < m;++i) scanf("%d%d", &e[i].first, &e[i].second); memset(in, 0,sizeof in); memset(out, 0,sizeof out); memset(f, -1,sizeof f); int cnt = 0; for (int i = 0;i < m;++i) { in[e[i].first]++; in[e[i].second]++; int t1 = find(e[i].first); int t2 = find(e[i].second); if (t1 != t2) f[t1] = t2; } int o=0; for (int i = 1;i <= n;++i) { find(i); if (f[i] == -1) o++; }//o == 说明图连通 for (int i = 1;i <= n;++i) if (in[i] & 1) cnt++; if (cnt == 0 || cnt == 2) { if (o == 1) printf("Yes"); else printf("No"); }else printf("No"); printf(" "); memset(in, 0,sizeof in); memset(f, -1,sizeof f); cnt = 0; for (int i = 0;i < m;++i) { out[e[i].first]++; in[e[i].second]++; } if (o > 1) puts("No"); else { vector<int> vec; for (int i = 1;i <= n;++i) { if (in[i] != out[i]) vec.push_back(i); } if (vec.size() != 2 && vec.size() != 0) puts("No"); else { if (vec.size() == 0) { puts("Yes"); continue; } int u = vec[0], v = vec[1]; if (in[u] - out[u] == 1 && in[v] - out[v] == -1) puts("Yes"); else if (in[u] - out[u] == -1 && in[v] - out[v] == 1) puts("Yes"); else puts("No"); } } } // printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC); return 0; }

B.-0你的电脑炸了

题意

判断给出的图是不是合法。

分析

4*4的格子中,每一个位置会出现指定的某些数字,但是由于覆盖的作用,只会看见最上面的1个,其他的被压在了下面。A覆盖了B,B覆盖了A,这样是明显不成立的,这题就是判断是不是会出现相互覆盖的情况,拓普排序。
ps:初始化的表要仔细打。。。
vector<int> have[5][5]; int a[5][5]; int in[10]; vector<int> G[10]; void init() { have[1][1].push_back(1); have[1][2].push_back(1), have[1][2].push_back(2); have[1][3].push_back(2), have[1][3].push_back(3); have[1][4].push_back(3); have[2][1].push_back(1), have[2][1].push_back(4); have[2][2].push_back(1), have[2][2].push_back(2), have[2][2].push_back(4), have[2][2].push_back(5); have[2][3].push_back(2), have[2][3].push_back(3), have[2][3].push_back(5), have[2][3].push_back(6); have[2][4].push_back(3), have[2][4].push_back(6); have[3][1].push_back(4), have[3][1].push_back(7); have[3][2].push_back(4), have[3][2].push_back(5), have[3][2].push_back(7), have[3][2].push_back(8); have[3][3].push_back(5), have[3][3].push_back(6), have[3][3].push_back(8), have[3][3].push_back(9); have[3][4].push_back(6), have[3][4].push_back(9); have[4][1].push_back(7); have[4][2].push_back(7), have[4][2].push_back(8); have[4][3].push_back(8), have[4][3].push_back(9); have[4][4].push_back(9); } void done(int u,int i, int j) { for (int k = 0;k < have[i][j].size();++k) { int v = have[i][j][k]; if (u == v) continue; G[u].push_back(v); in[v]++; } } void getmap() { for (int i = 1;i <= 9;++i) { G[i].clear(); in[i] = 0; } for (int i = 1;i <= 4;++i) { for (int j = 1;j <= 4;++j) done(a[i][j], i, j); } } void solve() { getmap(); queue<int> que; for (int i = 1;i <= 9;++i) { if (in[i] == 0) { que.push(i); } } while(!que.empty()) { int u = que.front(); que.pop(); for (int i = 0;i < G[u].size();++i) { int v = G[u][i]; if (--in[v] == 0) { que.push(v); } } } bool ok = true; for (int i = 1;i <= 9;++i) if (in[i] > 0) ok = false; if (ok) puts("Lucky dog!"); else puts("BOOM!"); } int main(int argc, const char * argv[]) { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); // clock_t _ = clock(); init(); int T; cin >> T; while(T--) { for (int i = 1;i <= 4;++i) { for (int j = 1;j <= 4;++j) scanf("%d", &a[i][j]); } solve(); } // printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC); return 0; }

C.寻觅fly真迹

题意

分析

首先用补图还是很容易想到的(毕竟正着弄相对复杂了)。建立补图以后很容易就想到了2分图染色,最后判断是不是成立。
const int maxn = 5e2 + 10; int n, m; int col[maxn]; vector<int> G[maxn]; int g[maxn][maxn]; bool dfs(int u,int color) { col[u] = color; for (int i = 0;i < G[u].size();++i) { int v = G[u][i]; if (col[u] == col[v]) return false; if (!col[v] && !dfs(v, -color)) return false; } return true; } int main(int argc, const char * argv[]) { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); // clock_t _ = clock(); int t; cin >> t; while(t--) { scanf("%d%d", &n, &m); memset(g, 0,sizeof g); int u, v; for (int i = 1;i <= m;++i) { scanf("%d%d", &u, &v); g[u][v] = g[v][u] = 1; } for (int i = 1;i <= n;++i) { G[i].clear(); for (int j = 1;j <= n;++j) if (i != j && !g[i][j]) G[i].push_back(j); } bool yes = true; memset(col, 0,sizeof col); for (int i = 1;i <= n;++i) { if (!col[i] && G[i].size() && !dfs(i, 1)) { yes=false; } } for (int i = 1;i <= n;++i) { for (int j = 1;j <= n;++j) { if (i == j) continue; if (g[i][j] && col[i]*col[j]<0)yes=false; if (!g[i][j] && col[i]*col[j]>=0)yes=false; } } if (yes) puts("Yes"); else puts("No"); } // printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC); return 0; }

D.1食堂or2食堂,it’s a question

题意

好懂,可能就“使得任意两人走过的距离加上2人所在食堂的距离的最大值最小”这句话需要解释下。任意两个人A, B 如果在同1个食堂的话就是他两个走过的距离和,如果不在同1个食堂就再加上两个食堂之间的距离。

分析

求最大最小,明显2分结果值。然后根据2分值建图判断可行性。
我们可以用bool值表示每一个人的选择。对第i个人而言,i表示其选择第1食堂,i+N表示其选择2食堂。
<1> 相互仇恨的两个人x,y
必定建立4条边(x,y+N), (y,x+N),(x+N,y),(y+N,x)。表示两个选择不同的食堂。
<2> 相互喜欢的两个人x,y
必定建立4条边(x,y),(y,x),(x+N,y+N),(y+N,x+N)表示两个人选择同1个食堂。
<3> 对人意的两个人x,y
这里就看代码了。。。
/***************************************** Author :Crazy_AC(JamesQi) Time :2016 File Name : _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---'\____ .' \| |// `. / \||| : |||// \ / _||||| -:- |||||- \ | | \\ - /// | | | \_| ''\---/'' | | \ .-\__ `-` ___/-. / ___`. .' /--.--\ `. . __ ."" '< `.___\_<|>_/___.' >'"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / / ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 佛祖保佑 永无BUG *****************************************/ // #pragma comment(linker, "/STACK:1024000000,1024000000") #include <iostream> #include <algorithm> #include <iomanip> #include <sstream> #include <string> #include <stack> #include <queue> #include <deque> #include <vector> #include <map> #include <set> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <climits> using namespace std; #define MEM(x,y) memset(x, y,sizeof x) #define pk push_back #define lson rt << 1 #define rson rt << 1 | 1 #define bug cout << "BUG HERE\n" typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> ii; typedef pair<ii,int> iii; const double eps = 1e⑻; const double pi = 4 * atan(1); const int inf = 1 << 30; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; int nCase = 0; int dcmp(double x){//精度正负、0的判断 if (fabs(x) < eps) return 0; return x < 0?-1:1; } inline int read(){ char c = getchar(); while (!isdigit(c)) c = getchar(); int x = 0; while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn = 2010; struct Edge{ int to, nxt; Edge() {} Edge(int to,int nxt) { this->to = to; this->nxt = nxt; } }edges[maxn*maxn]; int N, A, B; int head[maxn], ecnt; void add(int u,int v) { edges[ecnt] = Edge(v, head[u]), head[u] = ecnt++; } int dfn[maxn], low[maxn], depth; bool in[maxn]; stack<int> st; int belong[maxn]; int block; void tarjan(int u) { dfn[u] = low[u] = ++depth; in[u] = true; st.push(u); for (int i = head[u]; ~i;i = edges[i].nxt) { int v = edges[i].to; if (dfn[v] == -1) { tarjan(v); low[u] = min(low[u], low[v]); }else if (in[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { block++; while(true) { int x = st.top(); st.pop(); in[x] = false; belong[x] = block; if (x == u) break; } } } struct point { int x, y; void read() { scanf("%d%d", &x, &y); } }p[maxn], hate[maxn], like[maxn], s1, s2; int dis[maxn][maxn]; inline int dist(point& a,point& b) {//曼哈顿距离 return abs(a.x - b.x) + abs(a.y - b.y); } bool ok() { depth = block = 0; memset(dfn, -1,sizeof dfn); for (int i = 1;i <= 2*N;++i) if (dfn[i] == -1) tarjan(i); for (int i = 1;i <= N;++i) if (belong[i] == belong[i+N]) return false; return true; } void getmap(int limit) { ecnt = 0; memset(head, -1,sizeof head); for (int i = 1;i <= A;++i) { add(hate[i].x, hate[i].y + N); add(hate[i].y, hate[i].x + N); add(hate[i].x + N, hate[i].y); add(hate[i].y + N, hate[i].x); } for (int i = 1;i <= B;++i) { add(like[i].x, like[i].y); add(like[i].y, like[i].x); add(like[i].x + N, like[i].y + N); add(like[i].y + N, like[i].x + N); } for (int i = 1;i <= N;++i) { for (int j = i + 1;j <= N;++j) { if (dis[i][N+1] + dis[j][N+1] > limit) {//不能1同食堂 add(i, j + N); add(j, i + N); } if (dis[i][N+2] + dis[j][N+2] > limit) { add(i + N, j); add(j + N, i); } if (dis[i][N+1] + dis[j][N+2] + dis[N+1][N+2] > limit) { add(i, j); add(j+N, i+N); } if (dis[i][N+2] + dis[j][N+1] + dis[N+1][N+2] > limit) { add(i+N,j+N); add(j, i); } } } } int main(int argc, const char * argv[]) { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); // clock_t _ = clock(); int T_T; scanf("%d", &T_T); while(T_T--) { scanf("%d%d%d", &N, &A, &B); s1.read(), s2.read(); dis[N+1][N+2] = dist(s1, s2); for (int i = 1;i <= N;++i) { p[i].read(); dis[i][N+1] = dist(p[i], s1); dis[i][N+2] = dist(p[i], s2); } for (int i = 1;i <= A;++i) hate[i].read(); for (int i = 1;i <= B;++i) like[i].read(); int low = 0, high = 50000000; int ans = -1; while(low <= high) { int mid = (low + high) / 2; getmap(mid); if (ok()) { ans = mid; high = mid - 1; }else low = mid + 1; } printf("%d\n", ans); } // printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC); return 0; }

E.Division

题意

分析

套路,缩点+匹配
const int N = 5000 + 10; const int M = 100000 + 10; int n, m; int head[N], pnt[M], nxt[M], cnt; void init() { memset(head, -1,sizeof head); cnt = 0; } void addedge(int u,int v) { pnt[cnt] = v, nxt[cnt] = head[u],head[u] = cnt++; } int dfn[N], low[N], belong[N]; int Times; stack<int> st; int scc; void Tarjan(int u) { dfn[u] = low[u] = ++Times; st.push(u); for (int i = head[u];~i;i = nxt[i]) { int v = pnt[i]; if (!dfn[v]) { Tarjan(v); low[u] = min(low[u], low[v]); }else if (!belong[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { ++scc; while(true) { int x = st.top(); st.pop(); belong[x] = scc; if (x == u) break; } } } vector<int> G[N]; int linker[N]; bool vis[N]; bool dfs(int u) { for (int i = 0;i < G[u].size();++i) { int v = G[u][i]; if (vis[v]) continue; vis[v] = true; if (linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } return false; } int Hungary(){ int ans = 0; memset(linker, -1,sizeof linker); for (int i = 1;i <= scc;++i) { memset(vis, false,sizeof vis); if (dfs(i)) ans++; } return ans; } int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); int u, v; for (int i = 1;i <= m;++i) { scanf("%d%d",&u,&v); addedge(u, v); } memset(dfn, 0,sizeof dfn); memset(belong, 0,sizeof belong); scc = Times = 0; for (int i = 1;i <= n;++i) G[i].clear(); for (int i = 1;i <= n;++i) if (!dfn[i]) Tarjan(i); for (int i = 1;i <= n;++i) { for (int j = head[i];~j;j = nxt[j]) { int v = pnt[j]; if (belong[i] != belong[v]) { G[belong[i]].push_back(belong[v]); } } } printf("%d\n", scc - Hungary()); } return 0; }

F.meixiuxiu学图论

题意

求所有环中的最大边权的最小值。

分析

可以两种做法。
1.2分结果然后scc.
2.最小生成树的利用.
说第2种吧。。。把边排序,然后合并第1个构成的环的最后1天边就是答案。
const int maxn = 5e5 + 10; const int maxm = 2e6 + 10; struct Edge { int u, v, c; Edge() {} Edge(int u,int v,int c) { this->u = u; this->v = v; this->c = c; } bool operator < (const Edge& rhs) const { return c < rhs.c; } void read() { scanf("%d%d%d", &u, &v, &c); } }e[maxm]; int f[maxn]; int find(int x) { return f[x] == -1?x : f[x] = find(f[x]); } int main(int argc, const char * argv[]) { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); // clock_t _ = clock(); int n , m; int t; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); for (int i = 0;i < m;++i) e[i].read(); sort(e,e+m); memset(f, -1,sizeof f); int ans = -1; for (int i = 0;i < m;++i) { int t1 = find(e[i].u); int t2 = find(e[i].v); if (t1 != t2) { f[t1] = t2; }else if (ans == -1) ans = e[i].c; } if (ans == -1) puts("No solution!"); else printf("%d\n", ans); } // printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC); return 0; }

G.最短路

题意

分析

问的是最短路的条数,且任意两条路不重复。首先每条路径都是最短的,所以就建立最短路树。然后就是最大流算法了。并附上最大流模版。。。
const int maxn = 1010; vector<ii> G[2][maxn];//v, cost int n, m; int dis1[maxn], dis2[maxn], in[maxn]; void spfa(int s,int t,int* d, int o) { for (int i = 1;i <= n;++i) d[i] = INF; memset(in, 0,sizeof in); d[s] = 0; queue<int> que; que.push(s); while(!que.empty()) { int u = que.front(); que.pop(); in[u] = 0; for (int i = 0;i < G[o][u].size();++i) { int v = G[o][u][i].first; int cost = G[o][u][i].second; if (d[v] > d[u] + cost) { d[v] = d[u] + cost; if (in[v] == 0) { in[v] = 1; que.push(v); } } } } } struct Edge{ int from, to, cap, flow; Edge(){} Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){} }; struct ISAP{ int p[maxn], num[maxn], cur[maxn], d[maxn]; int s, t, n, m; bool vis[maxn]; vector<int> G[maxn]; vector<Edge> edges; void init(int n) { this->n = n; for (int i = 0;i <= n;++i) { G[i].clear(); d[i] = INF; } edges.clear(); } void addedge(int from,int to,int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = (int)edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool bfs() { memset(vis, false,sizeof vis); queue<int> que; d[t] = 0; vis[t] = true; que.push(t); while(!que.empty()) { int u = que.front(); que.pop(); for (int i = 0;i < G[u].size();++i) { Edge& e = edges[G[u][i]^1]; if (e.cap > e.flow && !vis[e.from]) { vis[e.from] = true; d[e.from] = d[u] + 1; que.push(e.from); } } } return vis[s]; } int Augment() { int u = t, flow = INF; while(u != s) { Edge& e = edges[p[u]]; flow = min(flow, e.cap - e.flow); u = edges[p[u]].from; } u = t; while(u != s) { edges[p[u]].flow += flow; edges[p[u]^1].flow -= flow; u = edges[p[u]].from; } return flow; } int MaxFlow(int s,int t) { this->s = s,this->t = t; int ret = 0; bfs(); if (d[s] >= n) return 0; memset(num, 0,sizeof num); memset(cur, 0,sizeof cur); for (int i = 0;i < n;++i) { if (d[i] < INF) num[d[i]]++; } int u = s; while(d[s] < n) { if (u == t) { ret += Augment(); u = s; } bool ok = false; for (int i = cur[u];i < G[u].size();++i) { Edge& e = edges[G[u][i]]; if (e.cap > e.flow && d[u] == d[e.to] + 1) { ok = true; p[e.to] = G[u][i]; cur[u] = i; u = e.to; break; } } if (!ok) { int Min = n - 1; for (int i = 0;i < G[u].size();++i) { Edge& e = edges[G[u][i]]; if (e.cap > e.flow) Min = min(Min, d[e.to]); } if (--num[d[u]] == 0) break; num[d[u] = Min + 1]++; cur[u] = 0; if (u != s) u = edges[p[u]].from; } } return ret; } }solve; int main(int argc, const char * argv[]) { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); // clock_t _ = clock(); int t; cin >> t; while(t--) { scanf("%d%d", &n, &m); for (int i = 1;i <= n;++i) G[0][i].clear(), G[1][i].clear(); int u, v, c; for (int i = 1;i <= m;++i) { scanf("%d%d%d", &u, &v, &c); G[0][u].push_back(ii(v, c)); G[1][v].push_back(ii(u, c)); } int st, ed; scanf("%d%d", &st, &ed); spfa(st, ed, dis1, 0); spfa(ed, st, dis2, 1); int limit = dis1[ed]; if (limit == INF) { printf("%d\n", 0); continue; } solve.init(n); for (int i = 1;i <= n;++i) { for (int j = 0;j < G[0][i].size();++j) { int k = G[0][i][j].first; if (dis1[i] != INF && dis2[k] != INF && dis1[i] + dis2[k] + G[0][i][j].second == limit) { solve.addedge(i, k, 1); } } } int ans = solve.MaxFlow(st, ed); printf("%d\n", ans); } // printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC); return 0; }

H.NightMare2

题意

从1号点到n号点在k的时间内逃出去的条件下,能带走的最大价值珠宝。

分析

又是1种套路。2分答案,然后跑最短路,看能不能逃出去。
/***************************************** Author :Crazy_AC(JamesQi) Time :2016 File Name : _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---'\____ .' \| |// `. / \||| : |||// \ / _||||| -:- |||||- \ | | \\ - /// | | | \_| ''\---/'' | | \ .-\__ `-` ___/-. / ___`. .' /--.--\ `. . __ ."" '< `.___\_<|>_/___.' >'"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / / ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 佛祖保佑 永无BUG *****************************************/ // #pragma comment(linker, "/STACK:1024000000,1024000000") #include <iostream> #include <algorithm> #include <iomanip> #include <sstream> #include <string> #include <stack> #include <queue> #include <deque> #include <vector> #include <map> #include <set> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <climits> using namespace std; #define MEM(x,y) memset(x, y,sizeof x) #define pk push_back #define lson rt << 1 #define rson rt << 1 | 1 #define bug cout << "BUG HERE\n" typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> ii; typedef pair<ii,int> iii; const double eps = 1e⑻; const double pi = 4 * atan(1); const long long inf = 1e20 + 10; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; int nCase = 0; int dcmp(double x){//精度正负、0的判断 if (fabs(x) < eps) return 0; return x < 0?-1:1; } inline int read(){ char c = getchar(); while (!isdigit(c)) c = getchar(); int x = 0; while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn = 1e4 + 10; struct Edge { int v, limit, cost; Edge() {} Edge(int v,int limit, int cost) { this->v = v; this->limit = limit; this->cost = cost; } }; vector<Edge> G[maxn];

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐