二分图染色+dp 31 pts 求条

31 pts:WA

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=107;
int n, cnt=0;
bool e[N][N], e2[N][N];
bool vis[N], col[N];
int sz[N][2];
vector<int> id[N][2];
bool dp[N][N];int pre[N][N];
bool pd[N];int pos[N];
void dfs(int x, bool co){
    sz[cnt][co]++;
    id[cnt][co].push_back(x);
    vis[x]=1;col[x]=co;
    for(int i=1;i<=n;i++){
        if(e2[x][i]){
            if(!vis[i])
                dfs(i, (co^1));
            else if(col[i]==col[x]){
                cout<<"No solution"<<endl;
                exit(0);
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int j;
        while((cin>>j) && j!=0)
            e[i][j]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(!(e[i][j] && e[j][i]) && (e[i][j] || e[j][i]))
                e2[i][j]=e2[j][i]=1;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt++;
            dfs(i, 1);
        }
    }
    dp[0][0]=1;
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<=n/2;j++){
            if(j>=sz[i][0] && dp[i-1][j-sz[i][0]])
                dp[i][j]=1, pre[i][j]=0;
            if(j>=sz[i][1] && dp[i-1][j-sz[i][1]])
                dp[i][j]=1, pre[i][j]=1;
        }
    }
    int ans=0;
    for(int i=n/2;i>=0;i--){
        if(dp[cnt][i]){
            ans=i;
            break;
        }
    }
    for(int i=cnt;i>=1;i--){
        for(int j=0;j<id[i][pre[i][ans]].size();j++)
            pd[pos[++pos[0]]=id[i][pre[i][ans]][j]]=1;
        ans-=sz[i][pre[i][ans]];
    }
    sort(pos+1, pos+pos[0]+1);
    cout<<pos[0]<<" ";
    for(int i=1;i<=pos[0];i++)
        cout<<pos[i]<<" ";
    cout<<endl;
    cout<<n-pos[0]<<" ";
    for(int i=1;i<=n;i++)
        if(!pd[i])
            cout<<i<<" ";
    cout<<endl;
    return 0;
}