二分图题单¶
Arpa’s overnight party and Mehrdad’s silent entering¶
题面翻译¶
题目描述¶
有2n个人围成一圈坐在桌子边上，每个人占据一个位子，对应这2n个人是n对情侣，要求情侣不能吃同一种食物，并且桌子上相邻的三个人的食物必须有两个人是不同的，只有两种食物（1或者是2），问一种可行分配方式。
思路¶
这道题的做法就是通过建立二分图然后跑二分图染色就可以了。
首先我们在每对情侣之间连边，表示他们2个吃的不一样。
然后对于相邻3个人中要有2个吃的不同的限制，我们就在2i−1和2i之间连边 因为这样就可以保证三个人中必定有2个吃的不同。
但是为什么这样建出来的图一定是二分图呢？
关于二分图有个性质，如果这个图不是二分图的话，那么就一定有奇环，如果没有，就一定是二分图。
我们假设2i和2i−1之间已经有一条路径，因为一个点只会有一个对应的情侣，所以这条路径一定是有x条情侣之间的边和x−1条相邻点之间的边组成的（这个可以画个图理解一下），再加上这条边，所以这个环就是偶环。
#include<bits/stdc++.h>
#define rep(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define per(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
#define int long long
#define pii pair<int,int>
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define rd read()
int read(){
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
void write(int out){
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int N=2e0+15;
const int INF=1e9+5;
const int MOD=998244353;
int n,x[N],y[N],ans[N];
vector<int>v[N];
bool vis[N];
void dfs(int x,int y){
ans[x]=y;
vis[x]=1;
for(int i=0; i<v[x].size(); i++)
{
int h=v[x][i];
if(!ans[h])dfs(h,3-y);
}
}
signed main(){
n=rd;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
v[x[i]].push_back(y[i]);
v[y[i]].push_back(x[i]);
}
for(int i=1;i<=n;i++){
v[i*2-1].push_back(i*2);
v[i*2].push_back(i*2-1);
}
for(int i=1;i<=n*2;i++)if(!vis[i])dfs(i,1);
for(int i=1;i<=n;i++)printf("%lld %lld\n",ans[x[i]],ans[y[i]]);
}
输入格式¶
第一行为客人数量
接下来n行，第i+1行表示第i对情侣男女坐的位置
输出格式¶
无解输出-1
否则输出n行，第i+1行分别为第i组男女所食的种类
如果有多组解，输出任意一组解（spj）
感谢@额冻豆腐 提供的翻译
题目描述¶
Note that girls in Arpa’s land are really attractive.
Arpa loves overnight parties. In the middle of one of these parties Mehrdad suddenly appeared. He saw \(n\) pairs of friends sitting around a table. \(i\) -th pair consisted of a boy, sitting on the \(a_{i}\) -th chair, and his girlfriend, sitting on the \(b_{i}\) -th chair. The chairs were numbered \(1\) through \(2n\) in clockwise direction. There was exactly one person sitting on each chair.
-
Each person had exactly one type of food,
-
No boy had the same type of food as his girlfriend,
-
Among any three guests sitting on consecutive chairs, there was two of them who had different type of food. Note that chairs \(2n\) and \(1\) are considered consecutive.
Find the answer for the Mehrdad question. If it was possible, find some arrangement of food types that satisfies the conditions.
输入格式¶
The first line contains an integer \(n\) ( \(1<=n<=10^{5}\) ) — the number of pairs of guests.
The \(i\) -th of the next \(n\) lines contains a pair of integers \(a_{i}\) and \(b_{i}\) ( \(1<=a_{i},b_{i}<=2n\) ) — the number of chair on which the boy in the \(i\) -th pair was sitting and the number of chair on which his girlfriend was sitting. It's guaranteed that there was exactly one person sitting on each chair.
输出格式¶
If there is no solution, print -1.
Otherwise print \(n\) lines, the \(i\) -th of them should contain two integers which represent the type of food for the \(i\) -th pair. The first integer in the line is the type of food the boy had, and the second integer is the type of food the girl had. If someone had Kooft, print \(1\) , otherwise print \(2\) .
If there are multiple solutions, print any of them.
样例 #1¶
样例输入 #1¶
3
1 4
2 5
3 6
样例输出 #1¶
1 2
2 1
1 2
King's Quest 由一个匹配扩展到所有情况¶
题面翻译
很久以前有一个老国王，他有\(N\)个儿子。在他的王国里面，也有\(N\)个漂亮的女孩。国王知道他的每个孩子喜欢哪一个女孩。国王的孩子们很年轻，比较花心，所以一个孩子可能喜欢好几个女孩。
国王让他的巫师为他的每个儿子找到他最喜欢的女孩，这样这个儿子就可以娶这个女孩了。国王的巫师也做到了这点要求——他为每个儿子选择了他可以结婚的女孩，即这个儿子必须喜欢选中的女孩。当然了，每个儿子只能选择一个女孩。
然而，国王说：“我喜欢你做的清单，但是我还是有点不满意。对于我的每个儿子，我想知道可以和他结婚的所有女孩。当然了，这前提必须是所有的儿子都要找到一个女孩。”
国王希望巫师为他解决的问题对于巫师来说太难了。为了保全巫师的脑袋，请你写一个程序帮助巫师。
Input
输入的第一行包含\(N\) - 国王的儿子数（\(1\) \(\le\) \(N\) \(\le\) \(2000\)）。 接下来每个国王的儿子的N行包含他喜欢的女孩的名单：第一个\(K_i\) - 他喜欢的女孩的数量，然后有\(K_i\)个不同的整数，从\(1\)到\(N\)表示女孩的编号。 所有\(K_i\)的总和不超过\(200000\)。
输入的最后一行是巫师所做的清单 - \(N\)个不同的整数：对于每个儿子，给出他将按照此列表结婚的女孩的编号。 保证这个清单是正确的，也就是说，每个儿子都喜欢这个清单里面他所要结婚的女孩。
Output
输出\(N\)行。对于每个国王的儿子，首先打印\(L_i\) - 他喜欢和可以结婚的不同女孩的数量。 在那之后，输出\(L_i\)个不同的整数表示那些女孩的编号，按升序排列。
题意：给出一个二分图的完全匹配，对于每个左部点，求出可以与之匹配是所有右部点，使得仍然可以构造出一组完全匹配。
观察样例我们发现，也该有某种联通的关系，或者交集的关系使得可以匹配。
我们向从王子向公主连边，然后再根据给出的一组匹配从公主向王子连边。我们发现再一个强连通分量中的王子和公主都可以两两任意匹配。
如何证明？如何思考？
一个scc意味着公主可以两两互相到达。因此一个公主被占用时总是可以找到另外一个公主来匹配。而非scc则没有这个性质。即我们考虑在一个scc中，王子顺序选择公主，因为默认可以随便选，因此最后一对王子和公主无论如何都也该匹配。如果非scc则不能保证如果如何都匹配。
// Problem: King's Quest
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA1327
// Memory Limit: 0 MB
// Time Limit: 13500 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
vector<int> e[N],v[N];
int stk[N],top;
int instk[N];
int dfn[N],low[N];
int tim;
int cnt;
int scc[N];
int n;
void add(int a,int b ){
e[a].pb(b);
}
void tarjan(int x){
dfn[x]=low[x]=++tim;
instk[x]=1;
stk[++top]=x;
for(auto v:e[x]){
if(!dfn[v]){
tarjan(v);
low[x]=min(low[v],low[x]);
}else if(instk[v])low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x]){
int y;
cnt++;
do{
y=stk[top--];
instk[y]=0;
scc[y]=cnt;
if(y>n)v[cnt].pb(y);
}while(y!=x);
}
}
signed main(){
while(~scanf("%lld",&n)){
top=0;
cnt=tim=0;
for(itn i=1;i<=n*2;i++){
while(e[i].size())e[i].pop_back();
scc[i]=instk[i]=dfn[i]=low[i]=0;
}
for(int i=1;i<=n;i++){
int a=rd;
while(a--){
add(i,rd+n);
}
}
for(int i=1;i<=n;i++){
int p=rd+n;
add(p,i);
}
for(int i=1;i<=n*2;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=cnt;i++){
sort(v[i].begin(),v[i].end());
}
for(int i=1;i<=n;i++){
cout<<v[scc[i]].size()<<' ';
for(auto c:v[scc[i]]){
cout<<c-n<<' ';
}
cout<<endl;
}
for(int i=1;i<=cnt;i++){
while(v[i].size())v[i].pop_back();
}
}
}
Sorting Slides¶
教授这次演讲一共要用 \(n\) 张幻灯片，这 \(n\) 张幻灯片按照演讲要使用的顺序已经用数字 \(1\sim n\) 编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。
现在我们用大写字母 A，B，C …… 再次将幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字和字母编号对应起来，对于每张幻灯片，检查它能否对应唯一的数字。
输入格式
有多组测试数据。对于每组测试数据：
-
第一行输入一个整数 \(n\)，表示有 \(n\) 张幻灯片。当 \(n\) 等于 \(0\) 时，输入结束，这组 \(n = 0\) 的测试数据不应被处理。
-
接下来 \(n\) 行，每行包括 \(4\) 个整数 \(x_{min}, x_{max}, y_{min}, y_{max}\)，表示幻灯片的坐标（幻灯片为矩形）。这 \(n\) 张幻灯片按其在输入文件中出现的顺序从前到后依次编号为
A，B，C…… -
接下来的 \(n\) 行，每行包括 \(2\) 个整数，依次为 \(n\) 个数字编号的坐标 \(x, y\)。保证没有数字落在幻灯片的边界上。
输出格式
对于每组测试数据，在第一行先输出 Heap，再输出测试数据的序号，用一个空格隔开，形如 Heap 1。
若存在幻灯片可以唯一对应某个数字，那么在第二行按字母表顺序输出字母以及所对应的数字编号，不同字母之间用空格隔开，形如 (A, 1) (B, 2)。否则，输出 none。
注意：除最后一组数据（\(n = 0\)）外，在每组数据输出结束后要多输出一个空行。
注意：本题对空格、空行十分敏感，请不要输出多余的空行、空格。
题意：有一个平面，平面上有一些矩形和一些数字。要求给每个矩形匹配一个数字，使得数字在矩形内部。问唯一的匹配方案。
求匹配方案我们直接用二分图匹配即可。判断唯一：对于每一个匹配我们断掉这条边重新跑二分图，如果匹配数没有减少，说明有第二种方案。
// Problem: Sorting Slides
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA663
// Memory Limit: 0 MB
// Time Limit: 3000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e2+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
struct Node{
int v,ban;
};
vector<Node> e[N];
struct Edge{
int x1,x2,y1,y2;
}rec[N];
int tt=0;
void add(int a,int b){
e[a].pb({b,0});
}
bitset<N> vis;
int n;
int match[N];
int dfs(int x){
for(auto v:e[x]){
if(v.ban)continue;
if(vis[v.v])continue;
vis[v.v]=1;
if(!match[v.v]){
match[v.v]=x;
return 1;
}else if(dfs(match[v.v])){
match[v.v]=x;
return 1;
}
}
return 0;
}
int bfs(){
int ans=0;
memset(match,0,sizeof match);
for(int i=1;i<=n;i++){
vis.reset();
ans+=dfs(i);
}
return ans;
}
void solve(){
n=rd;
if(!n)exit(0);
for(int i=1;i<=n;i++){
rec[i]={rd,rd,rd,rd};
}
for(itn i=1;i<=n;i++){
int x=rd,y=rd;
for(int j=1;j<=n;j++){
if(rec[j].x1<=x && x<=rec[j].x2 && rec[j].y1<=y && y<=rec[j].y2)
add(j, i);
}
}
printf("Heap %lld\n",++tt);
bool flg=0;
for(int x=1;x<=n;x++){
// cdbg(x);
for(int i=0;i<e[x].size();i++){
e[x][i].ban=1;
if(bfs()!=n){
if(flg)putchar(' ');
printf("(%c,%lld)",(char)x+'A'-1,e[x][i].v);
flg=1;
}
e[x][i].ban=0;
}
}
if(!flg){
puts("none");
}else puts("");
puts("");
for(int i=1;i<=n;i++){
while(e[i].size()){
e[i].pop_back(); // !!
}
}
}
signed main(){
while(1){
solve();
}
}