题意：
给出已0 1染色的无向图(不一定联通)，一次操作为一对相邻点颜色互换.
问使任意相邻点颜色不同，最少需要多少次操作
分析：
交换两点的代价即为两点间最短路.
故用BFS找出所有点到任意点的最短距离，并记录路径.
对于每个连通块，按照相邻点颜色不同重新染色一遍，若发现已给的01数目与染色需要01数目不符，则不可能
不然 ，则根据已给的01数目与染色需要01数目，确定匹配的点集.
最后KM算法算出最小权值匹配即可
确定匹配后，分析下同一路上的交换顺序，确定交换步骤
不算难，就是麻烦
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=;
const int MAXM = *; int map[MAXN][MAXN];//二分图描述
int linker[MAXN],lx[MAXN],ly[MAXN];
int slack[MAXN];
int nx,ny;
bool visx[MAXN],visy[MAXN]; bool DFS(int x)
{
int y;
visx[x] = ;
for(y = ;y < ny; ++y)
{
if(visy[y]) continue;
int tmp = lx[x] + ly[y] - map[x][y];
if(tmp == )
{
visy[y] = ;
if(linker[y] == - || DFS(linker[y]))
{
linker[y] = x;
return ;
}
}
else if(slack[y] > tmp)
slack[y] = tmp;
}
return ;
}
int KM()
{
for(int i = ;i < nx; ++i) linker[i] = -,ly[i] = ;
for(int i = ;i < nx; ++i)
{
lx[i] = -INF;
for(int j = ;j < ny; ++j)
if(map[i][j] > lx[i])
lx[i] = map[i][j];
}
for(int x = ;x < nx; ++x)
{
for(int i = ;i < ny; ++i) slack[i] = INF;
while()
{
for(int i = ;i < nx; ++i) visx[i] = ;
for(int i = ;i < ny; ++i) visy[i] = ;
if(DFS(x)) break;
int d = INF;
for(int i = ;i < ny; ++i)
if(!visy[i] && d > slack[i])
d = slack[i];
for(int i = ;i < nx; ++i)
if(visx[i])
lx[i] -= d;
for(int i = ;i < ny; ++i)
if(visy[i]) ly[i] += d;
else slack[i] -= d;
}
}
int res = ;
for(int i = ;i < ny;++i)
if(linker[i] != -)
res += map[ linker[i] ][i];
return res;
} int g[MAXN][MAXN],col[MAXN];
vector<int> X,Y,Left,Right;//X 1 Y 0
char s[MAXN];
int n,m,ans;
queue<int> p;
vector<int> G[MAXN]; bool BFS(int x,int c)//染色
{
while(!p.empty()) p.pop();
col[x] = c;
if(c) X.push_back(x);
else Y.push_back(x);
p.push(x);
int size,i;
while(!p.empty())
{
x = p.front(); p.pop();
size = G[x].size();
for(i = ; i < size; ++i)
{
if(col[ G[x][i] ] == col[x] ) return ;
else if(col[ G[x][i] ] == -)
{
col[ G[x][i] ] = col[x]^;
if( col[ G[x][i] ] ) X.push_back( G[x][i] );//1
else Y.push_back( G[x][i] );//0
p.push( G[x][i] );
}
}
}
return ;
}
vector<int> path[MAXN][MAXN];
int vis[MAXN],Pair1[MAXN],Pair2[MAXN],*Pair;
pair<int,int> Ans[MAXM];//答案 void GetPath(int u)//找到最短路并记录路径
{
int i, t, v;
for(i = ; i <= n; ++i) vis[i] = ;
while(!p.empty()) p.pop();
p.push(u);
path[u][u].push_back(u);
vis[u] = ;
g[u][u] = ;
while(!p.empty())
{
t = p.front(); p.pop();
for(i = ; i < G[t].size(); ++i)
{
v = G[t][i];
if( !vis[v] )
{
vis[v] = ;
g[u][v] = g[u][t] + ;
path[u][v] = path[u][t];
path[u][v].push_back(v);
p.push(v);
}
}
}
}
int GetSum(vector<int> &X,vector<int> &Y,int Pair[])//匹配
{
int i,j;
Left.clear(); Right.clear();
for( i = ; i < X.size(); ++i)
{
if(s[ X[i] ] == '') Left.push_back( X[i] );
}
for( i = ; i < Y.size(); ++i)
{
if(s[ Y[i] ] == '') Right.push_back( Y[i] );
}
nx = Left.size();
ny = Right.size();
for( i = ; i< nx; ++i)
{
for( j = ;j< ny; ++j)
{
int x = Left[i],y = Right[j];
map[i][j] = -g[x][y];
}
}
int sum = KM();
for(i = ; i < nx; ++i)
{
int v = Right[i] ;
int u = Left[ linker[i] ];
Pair[u] = v; Pair[v] = u;//1 0
}
return -sum;
}
void GetAns(int u,int v)
{
int i, j, k;
if(s[u] != '') swap( u, v);
vector<int> &p = path[u][v];
for(i = ; i < p.size(); i = j)
{
for(j = i; j<p.size() && s[ p[j] ] == ''; ++j); //路上第一个'1'
if(j == p.size()) break;
for(k = j; k > i; --k)
{
Ans[ans++] = make_pair(p[k], p[k - ]);
swap(s[ p[k] ],s[ p[k-] ]);
}
}
}
int solve(int st)//当前连通分支
{
int i, zero = , col0 = ;
X.clear(); Y.clear();
if(!BFS(st, )) return ;//染色
for(i = ; i < X.size(); ++i)
{
if(s[X[i]] == '') ++zero;
}
for(i = ; i < Y.size(); ++i)
{
if(s[Y[i]] == '') ++zero;
}
int sum1=INF,sum2=INF;
if(zero == Y.size() )// '0' 与 0 的数目相等，X中'0'与Y中'1'对换
{
sum1 = GetSum(X, Y, Pair1);
}
if(zero == X.size() )// '0' 与 1 的数目相等，X中'1'与Y中'0'对换
{
sum2 = GetSum(Y, X, Pair2);
}
if(sum1 == INF && sum2 == INF) return ;
if(sum1 < sum2) Pair = Pair1;
else Pair = Pair2;
for(i=;i<X.size(); ++i)
{
if(Pair[ X[i] ] != -) GetAns(X[i], Pair[ X[i] ]);
}
return ;
}
int main()
{
int i,j,t;
scanf("%d", &t);
while(t--)
{
scanf("%d%d%s", &n, &m, s+);
for(i = ; i <= n; ++i) G[i].clear();
for(i = ; i <= n; ++i)
{
for(j = ; j <= n; ++j)
{
g[i][j] = INF;
}
}
for(i = ;i <= m; ++i)
{
int x,y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
for(i = ; i <= n; ++i)
for(j = ; j <= n; ++j)
path[i][j].clear();
for(i = ; i <= n; ++i) GetPath(i);//最短路
for(i = ; i <= n; ++i)
{
Pair1[i] = Pair2[i] = col[i] = -;
}
bool flag=;
ans = ;
for(i = ;i <= n; ++i)//对每个连通分支
{
if(col[i]==-&&!solve(i))
{
flag = ; break;
}
}
if(!flag)
{
puts("-1"); continue;
}
printf("%d\n",ans);
for(i = ; i< ans ;++i)
printf("%d %d\n",Ans[i].first, Ans[i].second);
}
return ;
}