Processing math: 100%

POJ1904 King's Quest 二分图+强连通分量

10 年前

题目大意:

给定一个二分图以及一组已知的完备匹配,要求对于每个X集合中的点确定这个点与哪些个Y集合中的点匹配时,依然能够存在完备匹配.

思路:

考虑完备匹配中,Xi−>Yi,Xj−>Yj,那么如果现在想要Xi−>Yj,那么就要保证这样做之后从Xj出发存在增广路,否则就不能形成完备匹配.

那么这条增广路的终点显然应该是Yi,也即存在必定存在路径Xj−>Yi.

我们考虑将之前给出的完备匹配的反向边连回去:即若存在匹配Xi−>Yi,则连接有向边Yi−>Xi.

那么我们考虑有路径Xj−>Yi−>Xi−>Yj−>Xj,就是说形成了一个环,那么这些点必定在一个强连通分量中!

考虑与某个点Xi在一个强连通分量一些Y集合的点Yk,若存在边Xi−>Yk,那么就是说Yk要么是Xi原来的完备匹配,要么可以通过交换重新找到增广路得到完备匹配.

因此我们求一次SCC就解决了这道题目.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#define _CRT_SECURE_NO_WARNINGS
 
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
 
#define N 2010
 
namespace Fio{
    inline int getc(){
#ifdef ONLINE_JUDGE
        static const int L=1<<15;
#else
        static const int L=1<<1;
#endif
        static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    inline bool digit(int c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[5000000],*o=buf;
    inline void putc(char c){*o++=c;}
    template<typename T>inline void print(T x){
        static int stk[100];int top=0;
        for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++='0'+stk[i];
    }
    inline void Final(){fwrite(buf,1,o-buf,stdout);}
}
 
int head[4010],next[2010*2010],end[2010*2010];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
 
int G[2010][2010],dfn[4010],low[4010],tclock,stk[4010],bel[4010],cnt,top;bool instk[4010];
 
void dfs(int x){
    dfn[x]=low[x]=++tclock;stk[++top]=x,instk[x]=1;
    for(int j=head[x];j;j=next[j]){
        if(!dfn[end[j]])dfs(end[j]),low[x]=std::min(low[x],low[end[j]]);
        else if(instk[end[j]])low[x]=std::min(low[x],dfn[end[j]]);
    }
    if(dfn[x]==low[x]){
        ++cnt;
        while(1){
            int i=stk[top--];instk[i]=0;
            bel[i]=cnt;
            if(i==x)break;
        }
    }
}
 
int seq[2010],id;
 
int main(){
    int n;Fio::Get(n);register int i,j;
    int t,x;for(i=1;i<=n;++i){Fio::Get(t);while(t--)Fio::Get(x),G[i][x]=1,addedge(i,n+x);}
 
    for(i=1;i<=n;++i)Fio::Get(x),addedge(n+x,i);
 
    for(i=1;i<=2*n;++i)if(!dfn[i])dfs(i);
 
    for(i=1;i<=n;++i){
        for(id=0,j=1;j<=n;++j)if(bel[i]==bel[n+j]&&G[i][j])seq[++id]=j;
        Fio::print(id);
        for(j=1;j<=id;++j)Fio::putc(' '),Fio::print(seq[j]);
        Fio::putc('\n');
        //printf("%d",id);
        //for(j=1;j<=id;++j)printf(" %d",seq[j]);
        //puts("");
    }
 
    Fio::Final();
 
#ifndef ONLINE_JUDGE
    system("pause");
#endif
    return 0;
}

 

Tags: 二分图 强连通分量
Posted in POJ | 0 Comments

BZOJ3012:[Usaco2012 Dec]First! Trie树+Tarjan求强连通分量

10 年前

思路:一开始的暴力思路是对于每个串,若想使得它成为字典序最小的串,就找到它和任意其他串的从前向后第一个字母不同的位置,并添加限制:这个串的该位置字母的字典序小于其他串的该位置字母的字典序.这样若限制无环,我们就说这个串可以是字典序最小的.

然而这样建图花费的时间太长.

若将所有的串插入一颗Trie树,考虑对于每个串,其需要考虑的限制仅仅是从根节点到串的结尾所对应的节点的路径上的分岔.这样限制数最多为O(L∗26),那么总的限制数最多为O(300000∗26),就可以暴力建图并利用TarjanCheck了.

(为什么没想到Trie树..)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 30010
#define L 300010
 
int ch[L][26],cnt,isend[L];
char s[L];int begin[N],len[N];
 
int G[26][26];
inline void reset(){memset(G,0,sizeof G);}
inline void addedge(int a,int b){/*printf("%d %d\n",a,b);*/G[a][b]=1;}
 
int dfn[26],low[26],tclock,stk[26],top,num;bool instk[26];
void dfs(int x){
    dfn[x]=low[x]=++tclock;stk[++top]=x,instk[x]=1;
    for(int j=0;j<26;++j)if(G[x][j]){
        if(!dfn[j])dfs(j),low[x]=min(low[x],low[j]);
        else if(instk[j])low[x]=min(low[x],dfn[j]);
    }if(dfn[x]==low[x]){
        ++num;
        while(1){int i=stk[top--];instk[i]=0;if(x==i)break;}
    }
}
inline bool judge(){
    memset(dfn,0,sizeof dfn);tclock=top=num=0;memset(instk,0,sizeof instk);
    for(int i=0;i<26;++i)if(!dfn[i])dfs(i);
    return num==26;
}
 
int ans[N],siz;
int main(){
    int n;cin>>n;
    register int i,j,k;
    int now=0;for(i=1;i<=n;++i)begin[i]=now,scanf("%s",s+now),len[i]=strlen(s+now),now+=len[i];
    int p,y;
    for(i=1;i<=n;++i){
        for(p=0,j=0;j<len[i];++j){if(!ch[p][y=s[begin[i]+j]-'a'])ch[p][y]=++cnt;p=ch[p][y];}
        isend[p]=i;
    }
    for(i=1;i<=n;++i){
        bool notok=0;
        for(reset(),p=0,j=0;j<len[i];p=ch[p][y],++j){
            if(isend[p]&&isend[p]!=i)notok=1;
            y=s[begin[i]+j]-'a';for(k=0;k<26;++k)if(k!=y&&ch[p][k])addedge(y,k);
        }
        if(!notok&&judge())ans[++siz]=i;
    }
    printf("%d\n",siz);
    //for(i=1;i<=siz;++i)printf("%d\n",ans[i]);
    for(i=1;i<=siz;++i){for(j=0;j<len[ans[i]];++j)putchar(s[begin[ans[i]]+j]);puts("");}
    return 0;
}

Tags: Trie 强连通分量
Posted in BZOJ | 0 Comments