前置核心知识：强连通分量（tarjan算法）
1，定义
给定n个集合（每个集合都是有2个元素），再给出m个关系式（形式大致是aVb==1),求是否能够从每个集合选一个元素，并且元素满足上述m条关系式的组合。
2，思想
由aVb==1我们可以确定的是a=0->b=1还有b=0->a=1。我们可以把每个集合看成0，1两个点（一个成立的组合必须使该集合为1或者0），对m条关系式都建立a=0->b=1还有b=0->a=1两条明确的有向边。
我们思考不成立的组合一定是存在一个点x，x=0能跑成x=1且x=1能跑出x=0（即x满足同时是1也是0，矛盾），也就是说x=0与x=1在一个环里面，因此，我们可以把给定的m条关系建边后，跑tarjan之后判定是否有一个集合是0与1在一个环的（那就不成立，否则成立）。
注意：
在求具体一个成立的集合时，一些集合是明确只能取一个值才符合题意的，eg：（我们设x表示集合x取0，x+n表示集合x取1）存在有向边：x->.......x+n,那么集合x只能取1，我们该如何判断其明确值呢，观察图我们发现x+n始终比x晚搜索到（因为只可能是x搜到x+n这个点，不存在x+n搜索到x这个点（否则成环矛盾），即x+n的拓扑序比x大（强连通分量scc较小）
所以对于一个集合，我们始终取x=(scc[x]>scc[x+n])而形成的组合一定是合法解中的一个
核心code
bool mjudge()
{for (int i = 1; i <= 2 * n; ++i)if (!dfn[i])tarjan(i);//一共n个集合，2*n个元素，对所以元素跑tarjanfor (int i = 1; i <= n; ++i)if (scc[i] == scc[i + n])return 0;//对n个集合判断是否有成环（不成立）return 1;
}3，习题1：Peaceful Commission
思路：
我们对于m条关系式的（a,b）（我们把所有点序号-1，使得同一个委员会的成员是异或关系），可以建立(a,b^1)的边，选择a,那么b所属的委员会一定不能选b，只能选b的另一个b^1。
之后判断是否存在这样的组合，存在，用dfs暴力出字典序最小即可
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f; //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 4e4 + 10;int n, m, dfn[N], low[N], sta[N], scc[N], head[N];
bool insta[N], vis[N];
int num, top, dfncnt, cnt;struct node
{int next, to;
} edge[N];void init()
{memset(head, 0, sizeof(head));memset(dfn, 0, sizeof(dfn));memset(vis, 0, sizeof(vis));num = top = cnt = dfncnt = 0;
}void add(int u, int v)
{edge[++num].next = head[u];edge[num].to = v;head[u] = num;
}void tarjan(int u)
{dfn[u] = low[u] = ++dfncnt;insta[u] = 1;sta[++top] = u;for (int i = head[u]; i; i = edge[i].next){int v = edge[i].to;if (!dfn[v]){tarjan(v);low[u] = min(low[u], low[v]);}else if (insta[v]){low[u] = min(dfn[v], low[u]);}}if (low[u] == dfn[u]){++cnt;while (1){int v = sta[top--];insta[v] = 0;scc[v] = cnt;if (u == v)break;}}}bool dfs(int u)//询问u点是否可以使用
{if (vis[u ^ 1])return 0;//如果同一个委员会另一人已经参加，他不能参加if (vis[u])return 1;//如果已经让他参加，直接返回1vis[u] = 1;//标记参加sta[++top] = u;//存入栈里面，方便后悔的时候取消访问的标记for (int i = head[u]; i; i = edge[i].next){int v = edge[i].to;if (!dfs(v))return 0;//u连向的所有v点（必须访问）只要有一个点不能访问，那么u点无法访问}return 1;//最终可以返回1
}bool jud()
{for (int i = 0; i < 2 * n; ++i)if (!dfn[i])tarjan(i);for (int i = 0; i < 2 * n; i += 2)if (scc[i] == scc[i ^ 1])return 0;//判断是否同一个委员会两人一起参加for (int i = 0; i < 2 * n; i += 2){if (!vis[i] && !vis[i ^ 1])//只有两人都没有参加过，才需要，有一人有参加已经符合情况{top = 0;//先把栈的指针指向0if (!dfs(i))//如果i不可以参加{while (top)vis[sta[top--]] = 0;//把存入栈的元素全部标记回去0if (!dfs(i ^ 1))return 0;//如果同一个委员会i^1还是不能参加，无解，返回0}}}return 1;
}int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int x, y;while (cin >> n >> m){init();for (int i = 1; i <= m; ++i){cin >> x >> y;--x, --y;add(x, y ^ 1);add(y, x ^ 1);}if (jud()){for (int i = 0; i < 2 * n; ++i)if (vis[i])cout << i + 1 << endl;//记得i一开始-1，要加回去}else cout << "NIE" << endl;}return 0;
}4,习题2：Building roads
思路：
1,求最小的最大距离——二分答案。
我们把两个仓库看成0与1，二分时每次选择一个最大距离max，如果i点与j点之间的连接方法大于这个max（假设i点连0，j点连0），我们可以确定，有两条确定的边（i=0,j=1),（j=0,i=1)，其余情况同理，因此，我们对所有点分情况建边，跑tarjan，成立则该max可行
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f; //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 1e3 + 10;int sta[N], dfn[N], scc[N], low[N], head[N], dis[N][3];
bool insta[N];
int num, top, dfncnt, cnt;int n, a, b, s[5][3], s12, like[N][3], hate[N][3];
struct node
{int next, to;
} edge[N * N];void init()
{memset(dfn, 0, sizeof(dfn));memset(head, 0, sizeof(head));num = top = dfncnt = cnt = 0;
}void add(int u, int v)
{edge[++num].next = head[u];edge[num].to = v;head[u] = num;
}void tarjan(int u)
{dfn[u] = low[u] = ++dfncnt;insta[u] = 1;sta[++top] = u;for (int i = head[u]; i; i = edge[i].next){int v = edge[i].to;if (!dfn[v]){tarjan(v);low[u] = min(low[u], low[v]);}else if (insta[v])low[u] = min(dfn[v], low[u]);}if (low[u] == dfn[u]){++cnt;while (1){int v = sta[top--];insta[v] = 0;scc[v] = cnt;if (u == v)break;}}
}bool mjudge(int mid)
{init();for (int i = 1; i <= n; ++i)for (int j = i + 1; j <= n; ++j)//建立任意两点之间在最大距离mid情况下可以确定的边{if (dis[i][0] + dis[j][0] > mid)add(i, j + n), add(j, i + n);if (dis[i][1] + dis[j][1] > mid)add(i + n, j), add(j + n, i);if (dis[i][0] + dis[j][1] + s12 > mid)add(i, j), add(j + n, i + n);if (dis[i][1] + dis[j][0] + s12 > mid)add(i + n, j + n), add(j, i);}//建立讨厌与喜欢的边for (int i = 1; i <= a; ++i){add(hate[i][0], hate[i][1] + n);add(hate[i][0] + n, hate[i][1]);add(hate[i][1], hate[i][0] + n);add(hate[i][1] + n, hate[i][0]);}for (int i = 1; i <= b; ++i){add(like[i][0], like[i][1]);add(like[i][0] + n, like[i][1] + n);add(like[i][1], like[i][0]);add(like[i][1] + n, like[i][0] + n);}//判断for (int i = 1; i <= n * 2; ++i)if (!dfn[i])tarjan(i);for (int i = 1; i <= n; ++i)if (scc[i] == scc[i + n])return 0;return 1;
}int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int x, y;while (cin >> n >> a >> b){cin >> s[0][0] >> s[0][1] >> s[1][0] >> s[1][1];s12 = abs(s[0][0] - s[1][0]) + abs(s[0][1] - s[1][1]);for (int i = 1; i <= n; ++i){cin >> x >> y;dis[i][0] = abs(s[0][0] - x) + abs(s[0][1] - y);//dis0表示到0点距离，dis1表示到1点距离dis[i][1] = abs(s[1][0] - x) + abs(s[1][1] - y);}for (int i = 1; i <= a; ++i)cin >> hate[i][0] >> hate[i][1];for (int i = 1; i <= b; ++i)cin >> like[i][0] >> like[i][1];int l = 0, r = 120000010, ans = -1;while (l <= r)//二分{int mid = (l + r) >> 1;// cout << mid << endl;if (mjudge(mid)){r = mid - 1;ans = mid;}else l = mid + 1;}cout << ans << endl;}return 0;
}
