说在前面：

终于搞完了二分图匹配，所以特意来总结一下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;
}