题解说的很清楚了……题目细节非常多。
题目大意：
给出一张图，并且黑白染色了。你可以交换任意【相邻】的2个颜色，最终最少多少次交换，可以让整个图变为一个二分图（相邻点黑白不同）。
A,B点如果要实现最终交换，如果A,B之间一共K个点，一定可以存在一个方法，使得通过交换A,B最短路上的点对在K步内完成交换。
先最短路预处理2点距离的信息。然后就先KM最小权匹配，得到哪些点之间实现交换，然后按照题解说的方法模拟输出即可。
PS：输出要小心小心小心 洋洋洒洒接近400行~模板太长了，细节太多了，能力太弱了，自己太笨了
数据生成器生成的数据并不大，但是时间够的话，应该能包含所有WA的情况了吧……
然后辅助
https://csacademy.com/app/graph_editor/这个网站，快速查出出错原因。讲解一下数据生成器用来对拍，路径输出实在细节略多……自己写了SPJ来对拍了……
你的程序是a.exe，然后执行x.exe即可。
make.exe用来生成数据，ac.exe用来检验输出的第一行是否正确，然后x.exe会调用make.exe和ac.exe获得一些数据，然后读入a.exe输出的东西，用来比照，判断输出是否合法，然后判断是否构成了二分图。 如果出现问题留言……我怕我最后给x.cpp给改坏了……
数据生成器：
make.cpp 生成make.exe
#include <cstdio> #include <stack> #include <cstring> #include <algorithm> #include <iostream> #include <ctime> #include <queue> #include <ext/pb_ds/priority_queue.hpp> using namespace std; #define pr(x) cout<<#x<<" = "<<x<<" " #define prln(x) cout<<#x<<" = "<<x<<endl //#define pr(x) x //#define prln(x) x typedef long long LL; const LL mod = 1e9 + 7; int n, m; int output[2][1000]; int get(int a,int b)//返回a~b之间的数字 { return rand()%(b-a+1)+a; } void pg(int l , int r, int h, int p) { cout<<get(l,r)<<" "<<get(h,p)<<endl; } int main() { srand(time(0)); ios::sync_with_stdio(false); int a[1000]; for (int i = 1;i<=16;++i)a[i]=i; //分为3个集合 //1~4匹配5~8 9:10:11:12 13:14-15:16 int T=1; cout<<T<<endl; while (T--) { random_shuffle(a+1,a+1+15); int n = 16,m=19; cout<<n<<" "<<m<<endl; int b[20]={0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,1}; random_shuffle(a+1,a+8 + 1); random_shuffle(a+9,a+12+1); random_shuffle(a+13,a+16+1); random_shuffle(b+1,b+8 + 1); random_shuffle(b+9,b+12+1); random_shuffle(b+13,b+16+1); for (int i = 1;i<=16;++i) cout<<b[i]; cout<<endl; for (int i = 1; i <= 10;++i) pg(1,4,5,8); for (int i = 1; i <= 5;++i) pg(9,10,11,12); for (int i = 1; i <=4;++i) pg(13,14,15,16); } return 0; } AC代码：ac.cpp c++11编译后生成 ac.exe
#include <cstdio> #include <stack> #include <cstring> #include <algorithm> #include <iostream> #include <queue> #include <ext/pb_ds/priority_queue.hpp> using namespace std; #define pr(x) cout<<#x<<" = "<<x<<" " #define prln(x) cout<<#x<<" = "<<x<<endl //#define pr(x) x //#define prln(x) x typedef long long LL; int n, m; using __gnu_pbds::pairing_heap_tag; typedef pair<int, int> pii; typedef __gnu_pbds::priority_queue<pii, greater<pii>, pairing_heap_tag> Heap; typedef Heap::point_iterator Hit; const int INF = 0x3f3f3f3f; const int maxn = 700 + 10; struct KM { int n; // 左右顶点个数(左右顶点的最大值，不存在的点补全，并且添上没用的边，放在后面都用一个数 vector<int> G[maxn]; // 邻接表 int W[maxn][maxn]; // 权值 int Lx[maxn], Ly[maxn]; // 顶标（执行完后所有顶标之和最小 int left[maxn]; // left[i]为右边第i个点的匹配点编号，-1表示不存在 bool S[maxn], T[maxn]; // S[i]和T[i]为左/右第i个点是否已标记 int slack[maxn]; // 松弛量 slack[y] = min(Lx[x] + Ly[y] - W[x][y]) void init(int n) { this->n = n; for (int i = 0; i < n; i++) G[i].clear(); memset(W, 0, sizeof(W)); } void add_edge(int u, int v, int w) { G[u].push_back(v); W[u][v] = w; } bool match(int u) { S[u] = true; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (Lx[u] + Ly[v] == W[u][v] && !T[v]) { T[v] = true; if (left[v] == -1 || match(left[v])) { left[v] = u; return true; } } else slack[v] = min(slack[v], Lx[u] + Ly[v] - W[u][v]); } return false; } void update() { int a = INF; for (int i = 0; i < n; i++) if (!T[i]) a = min(a, slack[i]); for (int i = 0; i < n; i++) { if (S[i]) Lx[i] -= a; if (T[i]) Ly[i] += a; else slack[i] -= a; } } void solve() { for (int i = 0; i < n; i++) { Lx[i] = *max_element(W[i], W[i]+n); left[i] = -1; Ly[i] = 0; } for (int u = 0; u < n; u++) { memset(slack, 0x3f, sizeof(slack)); for (;;) { memset(S, 0, sizeof(S)); memset(T, 0, sizeof(T)); if (match(u)) break; update();//如果相等子图没有完美匹配，就更新顶标 } } } } km; const Hit null; struct Edge { int from, to, dist; }; struct Dijkstra { int n, m; vector<Edge> edges; vector<int> G[maxn]; bool done[maxn]; // 是否已永久标号 int d[maxn]; // s到各个点的距离 int p[maxn]; // 最短路中的上一条弧 Hit iter[maxn]; //i在堆中的迭代器 void init(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void add_edge(int from, int to, int dist) { edges.push_back((Edge){from, to, dist}); m = edges.size(); G[from].push_back(m-1); } void dijkstra(int s) { Heap q; for(int i = 0; i < n; i++) { d[i] = INF; iter[i] = null; } d[s] = 0; memset(done, 0, sizeof(done)); iter[s] = q.push(pii(0, s)); while(!q.empty()) { int u = q.top().second; q.pop(); if(done[u]) continue; done[u] = true; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; if (iter[e.to] != null) { q.modify(iter[e.to], pii(d[e.to], e.to)); } else iter[e.to] = q.push(pii(d[e.to], e.to)); } } } } // dist[i]为s到i的距离，paths[i]为s到i的最短路径（经过的结点列表，包括s和t） void get_shortest_paths(int s, vector<int>* paths) { dijkstra(s); for(int i = 0; i < n; i++) { if (d[i] == INF) continue; //prln(i); paths[i].clear(); int t = i; paths[i].push_back(t); while(t != s) { //prln(t); // getchar(); paths[i].push_back(edges[p[t]].from); t = edges[p[t]].from; } reverse(paths[i].begin(), paths[i].end()); } } } dj; char init_state[maxn]; int dist[maxn][maxn]; vector<int>g[maxn]; int colo[maxn], belong[maxn], block_cnt; vector<int>path[maxn]; queue<int>q; void init() { scanf("%d%d", &n, &m); scanf("%s", init_state); for (int i = 0; i != n; ++ i) init_state[i]-='0'; for (int i = 0; i != n; ++ i) g[i].clear(); dj.init(n); while (m--) { int a, b; scanf("%d%d", &a, &b); a--; b--; dj.add_edge(a, b, 1); dj.add_edge(b, a, 1); g[a].push_back(b); g[b].push_back(a); } for (int i = 0; i < n; ++ i) belong[i] = colo[i] = 0;//0为无色，1为黑，0为白 block_cnt = 0; //图可能多个连通快，对每个连通块进行编号，对每个连通快求最小值 for (int i = 0; i < n; ++ i) if (!belong[i]) { //prln(i); q.push(i); belong[i] = ++block_cnt; while (!q.empty()) { int now = q.front(); q.pop(); for (auto x : g[now]) if (!belong[x]) { belong[x] = block_cnt; q.push(x); } } } for (int i = 0; i < n; ++ i) { dj.dijkstra(i); for (int j = 0; j <n;++j) dist[i][j] = dj.d[j]; // dj.get_shortest_paths(i, dist[i], path[i]); } } bool ranse(int k)//给k节点染flag色 返回-1表示无解 { for (auto x : g[k]) { if (colo[x] == colo[k]) return false; if (!colo[x]) { colo[x] = 3 - colo[k]; if (!ranse(x)) return false; } } return true; } struct sx{int u,v;}; vector<int>hei, bai;//哪些黑色是错的，哪些白色是错的 vector<sx> output[maxn]; int liantongkuai[maxn]; int st[maxn]; int solve(int block, int flag)//求第block块,第一个染成colo色 { int now; for (int i = 0; i < n; ++ i) if (belong[i] == block) now = i; memset(colo, 0, sizeof(colo)); colo[now] = flag; if (!ranse(now)) return INF; int init_bai = 0, init_hei=0, bai_cnt=0, hei_cnt=0; for (int i = 0; i < n; ++ i) if (belong[i] == block) { if (init_state[i]==1) ++init_hei; if (init_state[i]==0) ++init_bai; if (colo[i] == 1) ++hei_cnt; if (colo[i] == 2) ++bai_cnt; } if (init_hei != hei_cnt || init_bai != bai_cnt) return INF; //剩下都是有解的情况 hei.clear(); bai.clear(); for (int i = 0; i < n; ++ i) if (belong[i] == block) { colo[i] %= 2; if (colo[i] != init_state[i]) { if (colo[i] == 1) { hei.push_back(i); }else { bai.push_back(i); } } } km.init(hei.size()); for (int i = 0; i != hei.size(); ++ i) for (int j = 0; j != bai.size(); ++ j) { //cout<<i<<" <-> "<<j<<endl; km.add_edge(i, j, -dist[hei[i]][bai[j]]); } km.solve(); int zongquan =0; for (int i = 0; i != hei.size(); ++ i) { int a = hei[km.left[i]]; int b = bai[i]; zongquan+= dist[a][b]; } if (zongquan >= liantongkuai[block]) return INF;//说明没有第一次的结果优 liantongkuai[block] = zongquan; output[block].clear(); for (int i = 0; i < n; ++ i) if (belong[i] == block) colo[i] = init_state[i]; for (int i = 0; i != hei.size(); ++ i) { int a = hei[km.left[i]]; int b = bai[i]; dj.get_shortest_paths(a, path); int top = 0; st[++top] = a; for (auto x : path[b]) { if (x==a) continue; if (colo[x] == colo[st[1]]) { st[++top] =x; }else { output[block].push_back({st[top], x}); swap(colo[st[1]], colo[x]); while (top>1) { output[block].push_back({st[top], st[top-1]}); --top; } st[top] = x; } } } return zongquan; } void doit() { int ans = 0; memset(liantongkuai, 0x3f, sizeof(liantongkuai)); //prln(block_cnt); for (int i = 1; i <= block_cnt; ++ i) { int a = solve(i, 2); int b = solve(i, 1); if (a == INF && b == INF) //无解 { printf("-1\n"); return; } } int tot=0; for (int i = 1; i<=block_cnt;++i) tot+= output[i].size(); printf("%d\n", tot); //为了对拍，不输出方案 for (int i = 1; i <= block_cnt; ++i) { for (int j = 0; j !=output[i].size(); ++ j) printf("%d %d\n", output[i][j].u + 1, output[i][j].v + 1); } } int main() { int T; scanf("%d", &T); while (T--) { init(); doit(); } return 0; } 对拍器：x.cpp 生成 x.exe
#include <cstdio> #include <stack> #include <cstring> #include <algorithm> #include <iostream> #include <ctime> #include <queue> #include <ext/pb_ds/priority_queue.hpp> using namespace std; #define pr(x) cout<<#x<<" = "<<x<<" " #define prln(x) cout<<#x<<" = "<<x<<endl //#define pr(x) x //#define prln(x) x typedef long long LL; const LL mod = 1e9 + 7; const int maxn = 1000; /* 1 16 19 0101001100111010 2 5 3 6 3 5 4 5 3 5 1 7 2 7 3 8 1 6 2 5 10 11 9 12 9 11 9 11 10 11 14 16 13 15 13 15 14 15 */ void makeit() { system("make>input.txt"); system("a<input.txt>a.out"); system("ac<input.txt>ac.out"); } int tong[1000][1000]; int n,m; int ans; char s[1000]; void init() { memset(tong,0,sizeof(tong)); FILE *input = fopen("input.txt", "r"); FILE *ac = fopen("ac.out","r"); int T; fscanf(input,"%d",&T); fscanf(input, "%d%d", &n, &m); fscanf(input, "%s", s+1); while (m--) { int a,b; fscanf(input,"%d%d", &a, &b); tong[a][b]=1; tong[b][a]=1; } fclose(input); fscanf(ac, "%d", &ans); fclose(ac); } int vis[maxn]; int dfs(int k) { vis[k] = 1; for (int i = 1;i<=n;++i) if (tong[k][i]) { if (i==k) continue; if (s[i] == s[k])//和后代颜色相同 { return false; } if (!vis[i]) dfs(i); } return true; } void doit() { int t; FILE *aout = fopen("a.out","r"); fscanf(aout,"%d", &t); if (t!=ans) { fclose(aout); cout<<"ans is ERROR!"<<endl; exit(0); } if (t==ans && t==-1) return;//无解的情况 while (t--) { int a,b; fscanf(aout, "%d%d", &a, &b); if (!tong[a][b]) { cout<<a<<" ->"<<b<<" not connect!"<<endl; exit(0); } swap(s[a], s[b]);//交换a,b的颜色 } //染色查看是否颜色都正确 //for (int i = 1; i <=n;++i) cout<<i<<" -"<<s[i]<<endl; memset(vis,0,sizeof(vis)); for (int i = 1;i<=n;++i) if (!vis[i]) { if (!dfs(i))//出现错误 { cout<<"colo is wrong"<<endl; exit(0); } } fclose(aout); } int main() { int t=0; while (1) { printf("第%d个数据了\n",t++); makeit(); init(); doit(); } return 0; }