40分,大佬们救救
查看原帖
40分,大佬们救救
1037841
zsjaaaxy楼主2024/8/15 12:51

目前只拿到了Impossible4个点的分,已知是判断的问题,但太菜了调了一个小时也没调对,请求路过的大佬们帮改改

#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int p1,p2;
}node[200005];
int n,m,u,v,sum[2]={0},ans=0;
bool col[200005]={0},vis[200005]={0};
queue<int> q[20005];
bool judge(int x,int color)
{
    if(vis[x]==true)
    {
        if(col[x]!=color)
        {
            return false;
        }
        return true;
    }
    else
    {
        vis[x]=true;
        col[x]=color;
        sum[color]++;
        while(!q[x].empty())
        {
           if(!judge(node[q[x].front()].p2,1-color))
           {
               return false;
           }
           q[x].pop();
        }
        return true;
    }
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        node[i].p1=u,node[i].p2=v;
        node[i+m].p1=v,node[i+m].p2=u;
        q[v].push(u);
        q[u].push(v);
    }
    for(int i=1;i<=n;i++)
    {
        sum[1]=0;
        sum[0]=0;
        if(vis[i]==true)
        {
            continue;
        }
        if(!judge(i,0))
        {
            cout<<"Impossible";
            return 0;
        }
        else
        {
            ans+=min(sum[0],sum[1]);
        }
    }
    cout<<ans;
    return 0;
}
2024/8/15 12:51
加载中...