#210. 【UER #6】寻找罪犯

71 阅读 0 评论 47 点赞

我是靠谱客的博主老实电话，最近开发中收集的这篇文章主要介绍#210. 【UER #6】寻找罪犯，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://uoj.ac/problem/210

开始就感觉是二分图

然后就弃T1后就一直想一直想

然而也没想出来

暴力都没法打啊......

题解确实是二分图算法四的优化也是非常神!!! 神的到现在也没看懂.....

60:

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream> 
#include<algorithm>
using namespace std;
const int N=800000;

struct H
{
    int x,nex;
}e[N*2];
int first[N],dfn[N],low[N],stk[N],v[N],bl[N],d[N];
int top,num,tot,cnt,ti,p,q,n,m,x,y,z,ans[N],c[N];

vector<pair<int,int> >V[N];
vector<int> E[N];

void add(int x,int y)
{
    e[++tot]=(H){y,first[x]};
    first[x]=tot;
    if(tot&1) add(y^1,x^1);
}
void dfs(int x)
{
    dfn[x]=low[x]=++ti;
    stk[++top]=x; v[x]=1;
    
    for(int i=first[x];i;i=e[i].nex)
        if(!dfn[e[i].x])
        {
            dfs(e[i].x);
            low[x]=min(low[x],low[e[i].x]);
        }
        else if(v[e[i].x])
            low[x]=min(low[x],dfn[e[i].x]);
            
    if(low[x]==dfn[x])
    {
        num++; v[x]=0;
        for(;stk[top]!=x;top--) 
            v[stk[top]]=0,bl[stk[top]]=num;
        bl[stk[top--]]=num;
    }
}
void f()
{
    for(int i=1;i<=num;i++)
        if(!d[i])
            c[++q]=i;
    
    for(p=1;p<=q;p++)
        for(int i=0;i<(int)E[c[p]].size();i++)
        {
             d[E[c[p]][i]]--;
             if(!d[E[c[p]][i]]) c[++q]=E[c[p]][i];
        }
    for(int i=2;i<=cnt;i++) dfn[bl[i]]=i;
    
    memset(v,0,sizeof(v));
    
    for(int i=1;i<=num;i++)
        if(!v[c[i]]) 
            v[bl[dfn[c[i]]^1]]=1;
    else 
        for(int j=0;j<(int)
            E[c[p]].size();j++)
    v[E[c[p]][j]]=1;
}

int main()
{
    scanf("%d%d",&n,&m); cnt=n*2+2;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        V[x].push_back(make_pair(y,z));
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(int)V[i].size();j++)
        {
            if(j) add(cnt,cnt-6),add(cnt+3,cnt-6);
             if(j!=(int)V[i].size()-1) 
            add(cnt+4,cnt+10),add(cnt+3,cnt+10);
            add(cnt+2,V[i][j].first*2+(!V[i][j].second));
            add(cnt+3,V[i][j].first*2+V[i][j].second);
            add(cnt,cnt+2); add(cnt+4,cnt+2);
            cnt+=6;
         }
         if(V[i].size()) add(i*2,cnt-6);
    }
    cnt--;
    for(int i=2;i<=cnt;i++) 
        if(!dfn[i]) dfs(i);
            for(int i=1;i<=n;i++)
                if(bl[i*2]==bl[i*2+1])
                {
                    puts("Impossible");
                    return 0;
                }
    for(int i=2;i<=cnt;i++) 
        for(int j=first[i];j;j=e[j].nex) 
            if(bl[e[j].x]!=bl[i]) 
                E[bl[e[j].x]].push_back(bl[i]);
                
    for(int i=1;i<=num;i++)
    {
        sort(E[i].begin(),E[i].end());
        E[i].erase(unique(E[i].begin(),E[i].end()),E[i].end());
    }
    for(int i=1;i<=num;i++) 
        for(int j=0;j<(int)E[i].size();j++) 
            d[E[i][j]]++;
    f();
    
    for(int i=1;i<=n;i++) 
        if(v[bl[i*2]]) 
            ans[++ans[0]]=i; 
            
    printf("%dn",ans[0]);
    for(int i=1;i<=ans[0];i++) printf("%d ",ans[i]);
    return 0;
}