Wuyanru's blog
0%

[QOJ10045] Permutation Recovery

发表于 分类于 ，

我爱构造，但是构造好像不爱我。

感觉我做过好类似的题但是这题还是没想出来（

题目链接。

题意

现在有 个 的排列，他们构成了一个 的矩阵，第 和 行分别是第 个排列和它的逆。

这个矩阵的每一列分别被打乱了，给出被打乱后的矩阵，构造一组原来的排列。

，。

题解

首先考虑，如果我们只是把所有排列本身塞到排列里，然后给出打乱的 的矩阵，这道题该怎么做。

我们发现，对于一个排列 ，我们可以建出一张图，边 存在当且仅当 。

那么一个排列建出来的有向图一定是若干个简单环。

我们发现，一张图能表示成若干个简单环，当且仅当每一个点入度出度都是 。

那么我们考虑建一张二分图出来，若 则我们给左侧的点 和右侧的点 连一条边。

这样我们建出的二分图是一张 正则图，也就是说每一个点的度数都恰好是 。

而我们知道，一张 正则图一定存在一组完美匹配，证明考虑 Hall 定理即可。

而一张 正则图，我们在去掉一组完美匹配之后，会变成 正则图，而我们还能继续找完美匹配。

也就是说，对于我们建出的 正则图，我们恰好可以找出 组不相交的完美匹配。

而每一组完美匹配恰好可以对应一个排列，这样我们就做完了上面的题目。

具体实现考虑直接用流跑二分图匹配，复杂度为 。

现在回到原问题，我们考虑一个排列 其对应的图，不难发现将其所有的边都反向之后就得到了 的图。

我们把 的图和 的图放到一起，就得到了一张无向图，其中每一个点度数为 ，并且这张无向图也是由若干个环组成的。

现在我们有 对互逆的排列，我们就能得到一张 个点的图，并且每一个点的度数都是 。

由于每一个点度数都是偶数，我们就可以跑一个欧拉回路出来。

考虑我们跑欧拉回路，其实相当于给每一条边定了一个方向，现在每一个点恰好有 个入度和 个出度。

不难发现，问题被转化成了之前所说的那个问题，直接流即可，复杂度 。

代码

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int cur[100005];
int head[100005];
int d[100005];
int to[750005];
int nx[750005];
int w[750005];

vc<int>gg[40005];
bool vis[280005];
vc<pi>g[40005];
int a[15][40005];
int n,k,c,S,T,cntm;
inline void add1(int u,int v)
{
    c++;
    g[u].push_back(pi(v,c));
    g[v].push_back(pi(u,c));
}
inline void ad(int u,int v,int ww)
{
    cntm++;
    to[cntm]=v;
    nx[cntm]=head[u];
    head[u]=cntm;
    w[cntm]=ww;
}
inline void add2(int u,int v,int w)
{
    ad(u,v,w);
    ad(v,u,0);
}
void dfs(int num)
{
    while(g[num].size())
    {
        int p=g[num].back().first;
        int id=g[num].back().second;
        g[num].pop_back();
        if(vis[id]) continue;

        gg[num].push_back(p);
        vis[id]=1,dfs(p);
    }
}
inline bool bfs()
{
    memset(d,0x3f,sizeof(int)*(T+1));
    queue<int>que;que.push(S),d[S]=0;
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=head[u];i;i=nx[i]) if(w[i])
        {
            int p=to[i],val=d[u]+1;
            if(val<d[p]) d[p]=val,que.push(p);
        }
    }
    return d[T]<=T;
}
int dfs(int u,int flow)
{
    if(u==T) return flow;
    int rest=flow;
    for(int &i=cur[u];i;i=nx[i]) if(w[i])
    {
        int p=to[i];
        if(d[p]!=d[u]+1) continue;
        int num=dfs(p,min(flow,w[i]));
        w[i]-=num,w[i^1]+=num,rest-=num;
        if(!rest) return flow;
    }
    return flow-rest;
}
inline void solve()
{
    memset(head,0,sizeof(head)),cntm=1;
    S=2*n+1,T=2*n+2;
    for(int i=1;i<=n;i++) add2(S,i,1),add2(i+n,T,1);
    for(int i=1;i<=n;i++) for(int p:gg[i]) add2(i,p+n,1);

    int ans=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        ans+=dfs(S,0x3f3f3f3f);
    }
    assert(ans==n);

    for(int i=1;i<=n;i++)
    {
        int A=-1;
        for(int j=head[i];j;j=nx[j]) if(!w[j]&&j!=S) A=to[j]-n;
        printf("%d%c",A," \n"[i==n]);
        gg[i].erase(find(gg[i].begin(),gg[i].end(),A));
    }
}
int main()
{
    n=read(),k=read();
    for(int i=1;i<=2*k;i++) for(int j=1;j<=n;j++) a[i][j]=read();
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<=2*k;j++)
        {
            if(a[j][i]==i) cnt++;
            else if(i<a[j][i]) add1(i,a[j][i]);
        }
        while(cnt) add1(i,i),cnt-=2;
    }
    for(int i=1;i<=n;i++) dfs(i);
    for(int i=1;i<=k;i++) solve();
    return 0;
}