二分图匹配题解

说在前面:

终于搞完了二分图匹配,所以特意来总结一下QAQ

NOI2009 变换序列

题目描述:

输入:

第一行包含一个整数N,表示序列的长度。接下来的一行包含N个整数Di,其中Di表示i和Ti之间的距离。

输出:

如果至少存在一个满足要求的变换序列T,则输出文件中包含一行N个整数,表示你计算得到的字典序最小的T;否则输出”No Answer”(不含引号)。

题解:

这道题首先你学要知道这个公式的意思是什么,上面这个指的是给你一个队列,这个队列是1到n的所有元素,并且代表着是你要求的一个队列和1到n这个顺序队列通过一个公式求出来的距离,公式:

1
d[i]=min(a[i]-b[i],n-|a[i]-b[i]|)

大概就是这样。

所以说我们可以通过上面的那个公式建立起来一个联系,也就是说,给定你的队列d是一个通过两种方法求出来的,分别是 a[i]-b[i]n-|a[i]-b[i]| ,我们需要判断他是由哪一个过来的,可能是其中一个,也有可能是其中的两个,这样我们将给定的队列和1-n进行连接,形成一个二分图。

建立起来二分图之后,我们就可以开始求要求的那个序列了也就是说,对于一个给定的序列d,有多中答案所对应的需要求出来的那个序列,题目上要求求出来字典序比较小的那一个,那么我们就可以用一个小小的贪心,在建立一个二分图的时候,我们将比较大的点留在后面,这样的话我们用邻接表访问的时候可以优先访问比较大的那个点(如果你用的是邻接矩阵的话直接进行倒序查找),然后我们在进行倒序循环,每次选择比较大的点进行匹配,这样的话后面的点选择的都是能选择的最大的点,这样的话就可以符合题目上面的要求,求出来字典序比较小的队列了。

最后进行数组匹配,然后按照顺序进行输出

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,d[20000],Get[20000];
int len,Link[20000],ans[20000];
bool vis[20000];
struct Edge
{
int Point;
int Next;
}a[40000];
inline int In()
{
int This=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') F=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
This=(This<<1)+(This<<3)+ch-'0';
ch=getchar();
}
return F*This;
}
int DIS(int x,int y)
{return min(abs(x-y),n-abs(x-y));}
int Line(int x,int y)
{
a[++len].Point=y;
a[len].Next=Link[x];
Link[x]=len;
}
bool DFS(int x)//匈牙利算法
{
for(int i=Link[x];i!=-1;i=a[i].Next)
if(!vis[a[i].Point])
{
int This=a[i].Point;
vis[This]=true;
if(!Get[This]||DFS(Get[This]))
{
Get[This]=x;
return true;
}
}
return false;
}
int main()
{
memset(Link,-1,sizeof(Link));
n=In();
for(int i=0;i<n;i++)
d[i]=In();
for(int i=0;i<n;i++)
{
int x=i+d[i];
int y=i-d[i]+n;
x%=n; y%=n;
if(DIS(x,i)!=d[i]) x=-1;
if(DIS(y,i)!=d[i]) y=-1;
if(x<y) swap(x,y);//将比较大的点放到优先访问的位置上面
if(x!=-1) Line(i,x);
if(y!=-1) Line(i,y);
}
for(int i=n-1;i>=0;i--)
{
memset(vis,false,sizeof(vis));
if(!DFS(i))
{
cout<<"No Answer"<<endl;
return 0;
}
}
for(int i=0;i<n;i++) ans[Get[i]]=i;//记录下来序列
for(int i=0;i<n;i++) cout<<ans[i]<<' ';
return 0;
}

NOIP2008 双栈排序

题目描述:

Tom最近在研究一个有趣的排序问题。如图所示,通过2个栈S1和S2,Tom希望借助以下4种操作实现将输入序列升序排序。

  1. 操作a: 如果输入序列不为空,将第一个元素压入栈S1
  2. 操作b:如果栈S1不为空,将S1栈顶元素弹出至输出序列
  3. 操作c:如果输入序列不为空,将第一个元素压入栈S2
  4. 操作d:如果栈S2不为空,将S2栈顶元素弹出至输出序列
  5. 如果一个1~n的排列P可以通过一系列操作使得输出序列为1,2,…,(n-1),n,Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”,而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列:<a,c,c,b,a,d,d,b>
  6. 当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。

输入:

第一行是一个整数n。
第二行有n个用空格隔开的正整数,构成一个1~n的排列。

输出:

共一行,如果输入的排列不是“可双栈排序排列”,输出数字0;否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

题解:

这道题超级魔性,最后还是看了题解才弄懂,不过现在再看看这道题,其实就是因为一个公式没有想出来,然后就不知道该如何进行求解了。

这解这道题的时候,我们需要明白如何求解这个栈,因为这个栈是有两个的,那么我们就需要分清楚那些点是必须在一起的,不能在一起的。而如何求出来那一个点必须在哪一个栈里面呢,我们需要引入一个公式,也就是对于对于每一个 i<j<k 如果有 a[k]<a[i]<a[j] 那么这两个数 a[i]a[j] 是不可以放到一个栈里面的。

这个公式的证明非常简单,用显然法即可。

那么我们就可以求出来那些点是可以在一起的,那些点不能在一起,然后我们就根据两个栈建立起来一个二分图,然后进行二分图匹配染色,这里的染色指的是判断那些点在一个集合里面。

最后我们在进行输出的时候就需要进行优先输出a和c,按照题意进行匹配就好,这里记住在if判断的时候一定要优先判断这个栈是否为空,然后在判断栈顶是否为This,如果这个栈空的,但是要求范围栈顶,那么就会出现错误的。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<stack>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,a[2000],F[2000];
int colour[2000],This=1;
bool Edge[2000][2000];
stack<int> Sta1,Sta2;
void DFS(int x,int num)
{
colour[x]=num;
for(int i=1;i<=n;i++)
if(Edge[x][i])
{
if(colour[i]==num)
{
cout<<0<<endl;
exit(0);
}
if(!colour[i])
DFS(i,3-num);
}
}
int main()
{
cin>>n; F[n]=123456789;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=n-1;i>=1;i--)
F[i]=min(F[i+1],a[i+1]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]<a[j]&&F[j]<a[i])
Edge[i][j]=true,Edge[j][i]=true;
for(int i=1;i<=n;i++)
if(!colour[i]) DFS(i,1);
for(int i=1;i<=n;i++)
{
if(colour[i]==1)
{
Sta1.push(a[i]);
cout<<"a ";
}
else {
Sta2.push(a[i]);
cout<<"c ";
}
while((!Sta1.empty()&&Sta1.top()==This)||(!Sta2.empty()&&Sta2.top()==This))
{
if(!Sta1.empty()&&Sta1.top()==This)
{
Sta1.pop();
cout<<"b ";
}
else {
Sta2.pop();
cout<<"d ";
}
This++;
}
}
return 0;
}