「BZOJ1093」[ZJOI2007] 最大半连通子图

第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。

应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

3
3

对于100%的数据， N ≤100000, M ≤1000000；对于100%的数据， X ≤10^8。

缩点。。。然后用拓扑排序找最长链。。

注意缩点后连通块间重边要处理下

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int mx,ans;
int ind,cnt,scc,top;
int n,m,X;
int last[100005],last2[100005];
int dfn[100005],low[100005],hav[100005],belong[100005],q[100005];
int r[100005],f[100005],g[100005],vis[100005];
bool inq[100005];
struct edge{int to,next;}e[2000005],ed[2000005];
void insert(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void ins(int u,int v)
{
    ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;
    r[v]++;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++ind;
    q[++top]=x;inq[x]=1;
    for(int i=last[x];i;i=e[i].next)
        if(!dfn[e[i].to])
            tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);
        else if(inq[e[i].to])low[x]=min(low[x],dfn[e[i].to]);
    int now=0;
    if(low[x]==dfn[x])
    {
        scc++;
        while(now!=x)
        {
            now=q[top];top--;
            inq[now]=0;
            hav[scc]++;
            belong[now]=scc;
        }
    }
}
void rebuild()
{
    cnt=0;
    for(int x=1;x<=n;x++)
    {
        for(int i=last[x];i;i=e[i].next)
            if(belong[x]!=belong[e[i].to])
                ins(belong[x],belong[e[i].to]);
    }
}
void dp()
{
    int head=0,tail=0;
    for(int i=1;i<=scc;i++)
	{
		if(!r[i])q[tail++]=i;
		f[i]=hav[i];g[i]=1;
	}
    while(head!=tail)
    {
        int now=q[head];head++;
        for(int i=last2[now];i;i=ed[i].next)
		{
			r[ed[i].to]--;
			if(!r[ed[i].to])q[tail++]=ed[i].to;
			if(vis[ed[i].to]==now)continue;
			if(f[now]+hav[ed[i].to]>f[ed[i].to])
			{
				f[ed[i].to]=f[now]+hav[ed[i].to];
				g[ed[i].to]=g[now];
			}
			else if(f[now]+hav[ed[i].to]==f[ed[i].to])
				g[ed[i].to]=(g[ed[i].to]+g[now])%X;
			vis[ed[i].to]=now;
		}
    }
}
int main()
{
    n=read();m=read();X=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        insert(u,v);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    rebuild();
    dp();
	for(int i=1;i<=scc;i++)
	{
		if(f[i]>mx)mx=f[i],ans=g[i];
		else if(f[i]==mx)ans=(ans+g[i])%X;
	}
    printf("%d\n%d\n",mx,ans);
    return 0;
}

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

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int mx,ans;

int ind,cnt,scc,top;

int n,m,X;

int last[100005],last2[100005];

int dfn[100005],low[100005],hav[100005],belong[100005],q[100005];

int r[100005],f[100005],g[100005],vis[100005];

bool inq[100005];

struct edge{int to,next;}e[2000005],ed[2000005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

void ins(int u,int v)

{

ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;

r[v]++;

}

void tarjan(int x)

{

dfn[x]=low[x]=++ind;

q[++top]=x;inq[x]=1;

for(int i=last[x];i;i=e[i].next)

if(!dfn[e[i].to])

tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);

else if(inq[e[i].to])low[x]=min(low[x],dfn[e[i].to]);

int now=0;

if(low[x]==dfn[x])

{

scc++;

while(now!=x)

{

now=q[top];top--;

inq[now]=0;

hav[scc]++;

belong[now]=scc;

}

void rebuild()

{

cnt=0;

for(int x=1;x<=n;x++)

{

for(int i=last[x];i;i=e[i].next)

if(belong[x]!=belong[e[i].to])

ins(belong[x],belong[e[i].to]);

}

void dp()

{

int head=0,tail=0;

for(int i=1;i<=scc;i++)

{

if(!r[i])q[tail++]=i;

f[i]=hav[i];g[i]=1;

}

while(head!=tail)

{

int now=q[head];head++;

for(int i=last2[now];i;i=ed[i].next)

{

r[ed[i].to]--;

if(!r[ed[i].to])q[tail++]=ed[i].to;

if(vis[ed[i].to]==now)continue;

if(f[now]+hav[ed[i].to]>f[ed[i].to])

{

f[ed[i].to]=f[now]+hav[ed[i].to];

g[ed[i].to]=g[now];

}

else if(f[now]+hav[ed[i].to]==f[ed[i].to])

g[ed[i].to]=(g[ed[i].to]+g[now])%X;

vis[ed[i].to]=now;

}

int main()

{

n=read();m=read();X=read();

for(int i=1;i<=m;i++)

{

int u=read(),v=read();

insert(u,v);

}

for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);

rebuild();

dp();

for(int i=1;i<=scc;i++)

{

if(f[i]>mx)mx=f[i],ans=g[i];

else if(f[i]==mx)ans=(ans+g[i])%X;

}

printf("%d\n%d\n",mx,ans);

return 0;

}

hzwer.com _ Home | http://hzwer.com

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论