39求调

clyCLY111 @ 2024-05-26 16:41:18

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,m,i,j,a[101][101],s[401],b[401],sum[401],id[401],t,ans,pre[101][101],k,x,l,r,res1,res2,f[401],g[101][101],ans1[101],ans2[101];
int find(int x){
    if(x==f[x]) return f[x];
    int root=find(f[x]);
    return f[x]=root;
}
void deal(int x,int y){
    f[find(x)]=find(y);
    return;
}
signed main(){
    cin>>n;
    for(i=1;i<=n;i++){
        while(cin>>x&&x!=0) a[i][x]=1;
        f[i]=i,f[i+n]=i+n;
    }
    for(i=1;i<n;i++){
        for(j=i+1;j<=n;j++){
            if(a[i][j]*a[j][i]==0){
                if(find(i)==find(j)){
                    cout<<"No solution"<<endl;
                    return 0;
                }
                deal(i,j+n),deal(j,i+n);
            }
        }
    }
    for(i=1;i<=n;i++){
        if(!b[find(i)]){
            id[++k]=i,b[find(i)]=1;
            for(j=1;j<=n;j++){
                if(find(i)==find(j)) sum[k]++;
            }
        }
    }
    g[0][0]=1;
    for(i=1;i<=k;i++){
        for(j=0;j<=n/2;j++){
            t=j-sum[i];
            if(t>=0&&g[i-1][t]) g[i][j]=1,pre[i][j]=1;
            t=j;
            if(g[i-1][t]) g[i][j]=1,pre[i][j]=0;
        }
    }
    for(i=n/2;i>=0;i--){
        if(g[k][i]){
            x=i;
            break;
        }
    }
    if(x==0){
        cout<<"No solution"<<endl;
        return 0;
    }
    for(i=k;i>=1;i--){
        if(pre[i][x]){
            x-=sum[i];
            for(j=1;j<=n;j++){
                if(find(id[i])==find(j)){
                    ans1[++res1]=j;
                }
            }
        }
        else{
            for(j=1;j<=n;j++){
                if(find(id[i])==find(j)){
                    ans2[++res2]=j;
                }
            }
        }
    }
    sort(ans1+1,ans1+1+res1),sort(ans2+1,ans2+1+res2);
    cout<<res1<<" ";
    for(i=1;i<=res1;i++) cout<<ans1[i]<<" ";
    cout<<endl<<res2<<" ";
    for(i=1;i<=res2;i++) cout<<ans2[i]<<" ";
    return 0;
}

by 123huchenghao @ 2024-06-29 20:49:14

#include <bits/stdc++.h>
using namespace std;
const int MN=105;
const int MM=105;
typedef long long ll;

bool g[MN][MN],f[MN][MN];
int n,num[MM][2],pre[MN][MN],ans;
vector<int> cont[MN][2];

int mtc[MN],sum=0;
void dfs(int x,int fa,int col)
{
    num[sum][mtc[x]=col]++;cont[sum][col].push_back(x);
    for (int i=1;i<=n;++i)
        if (!g[i][x] && i!=fa && x!=i)
        {
            if (mtc[i]==-1) dfs(i,x,col^1);
            else if (mtc[i]==col) {printf("No solution");exit(0);}
        }
}
void dp()
{
    f[0][0]=true; //as a beginner.
    for (int i=1;i<=sum;++i)
        for (int j=0;j<=n/2;++j)
        {
            int t=j-num[i][0];
            //what can be carried must be the best one.
            if (t>=0&&f[i-1][t]) f[i][j]=true,pre[i][j]=0;
            t=j-num[i][1];
            if (t>=0&&f[i-1][t]) f[i][j]=true,pre[i][j]=1;
        }
    for (int i=n/2;i>=0;--i) if (f[sum][i]) {ans=i;break;}
}
void print()
{
    int res[MN]={0},t=ans;
    bool p[MN]={false};
    for (int i=sum;i>0;--i)
    {
        for (int j=0;j<cont[i][pre[i][t]].size();++j) p[res[++res[0]]=cont[i][pre[i][t]][j]]=true;
        t-=num[i][pre[i][t]];
    }
    sort(res+1,res+res[0]+1);
    printf("%d ",res[0]);for (int i=1;i<=res[0];++i) printf("%d ",res[i]);
    printf("\n%d ",n-res[0]);for (int i=1;i<=n;++i) if (!p[i]) printf("%d ",i);
}
ll read(){
    ll f=1,x=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    n=read();
    int m,v;
    for (int i=1;i<=n;++i)
    {
        v=-1;
        while (v!=0){v=read();g[i][v]=true;}
    }
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j)
        {
            if (!(g[i][j]&&g[j][i]) && (g[i][j]||g[j][i])) g[i][j]=g[j][i]=false;
        }
    memset(mtc,-1,sizeof(mtc));
    for (int i=1;i<=n;++i)
        if (mtc[i]==-1)
        {
            sum++;
            dfs(i,0,1);
        }
    dp();
    print();
    return 0;
}