题解

mlvx · 2024-09-07 16:17:18 · 题解

题意

一个 n\times n 的方阵，里面有 m 个点，选中至少一个点，使得每行每列被选中点数相同。

分析

方格中对于行与列需要满足某种特征的题面，往往可以建图来解决。

每一行，每一列，分别对应一个编号。

例如 (u,v) 处有一个点，那我们就把 u 和 v+n 连边。

此时我们发现，这个图是个二分图，虽然在本题中并没有什么用。

现在问题就变成了找出图的一个子图，使得其中所有点的度数的奇偶性相同。

环上的点的度数都是偶数，故找出环即为找出偶数解的情况。

void dfs1(int x){
    vis[x]=1;
    for(auto[y,w]:g[x])if(!Vis[w]){
        Vis[w]=1,last[y]=x,from[x]=w;
        if(vis[y]){
            int cnt=0;puts("TAK");
            for(int tmp=last[y];tmp!=y;)++cnt,tmp=last[tmp];
            cout<<cnt+1<<'\n'<<from[y]<<' ';
            for(int tmp=last[y];tmp!=y;)cout<<from[tmp]<<' ',tmp=last[tmp];
            exit(0);
        }dfs1(y);
    }
}

不难发现图中如果没有环，那么这个图就是个森林。

由于叶子的度数是 1，所以所有点的度数都得是奇数。

注意到想要改变度数只能改变这个节点和其父亲的连边情况，所以从叶子节点向上进行改变即可。

void dfs2(int x){
    vis[x]=1;
    for(auto[y,w]:g[x])if(!vis[y])dfs2(y),dp[y]||(dp[x]^=1,ans[y]=w);
}

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=5e5+10;
int n,m,u,v,vis[N<<1],from[N<<1],last[N<<1],dp[N<<1],ans[N<<1],Vis[M];vector<pair<int,int>>g[N<<1];
void dfs1(int x){
    vis[x]=1;
    for(auto[y,w]:g[x])if(!Vis[w]){
        Vis[w]=1,last[y]=x,from[x]=w;
        if(vis[y]){
            int cnt=0;puts("TAK");
            for(int tmp=last[y];tmp!=y;)++cnt,tmp=last[tmp];
            cout<<cnt+1<<'\n'<<from[y]<<' ';
            for(int tmp=last[y];tmp!=y;)cout<<from[tmp]<<' ',tmp=last[tmp];
            exit(0);
        }dfs1(y);
    }
}void dfs2(int x){
    vis[x]=1;
    for(auto[y,w]:g[x])if(!vis[y])dfs2(y),dp[y]||(dp[x]^=1,ans[y]=w);
}int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>u>>v,g[u].push_back({v+n,i}),g[v+n].push_back({u,i});
    for(int i=1;i<=(n<<1);i++)if(!vis[i])dfs1(i);
    memset(vis,0,sizeof vis);
    for(int i=1;i<=(n<<1);i++)if(!vis[i]){dfs2(i);if(!dp[i])return puts("NIE"),0;}
    puts("TAK");int cnt=0;
    for(int i=1;i<=(n<<1);i++)if(ans[i])++cnt;
    cout<<cnt<<'\n';
    for(int i=1;i<=(n<<1);i++)if(ans[i])cout<<ans[i]<<' ';
    return 0;
}