題面：

2788: [Poi2012]Festival

Time Limit:?30 Sec??Memory Limit:?64 MB
Submit:?418??Solved:?190
[Submit][Status][Discuss]

Description

有n個正整數(shù)X1,X2,...,Xn，再給出m1+m2個限制條件，限制分為兩類：

1. 給出a,b (1<=a,b<=n)，要求滿足Xa + 1 = Xb

2. 給出c,d (1<=c,d<=n)，要求滿足Xc <= Xd

在滿足所有限制的條件下，求集合{Xi}大小的最大值。

Input

第一行三個正整數(shù)n, m1, m2 (2<=n<=600, 1<=m1+m2<=100,000)。

接下來m1行每行兩個正整數(shù)a,b (1<=a,b<=n)，表示第一類限制。

接下來m2行每行兩個正整數(shù)c,d (1<=c,d<=n)，表示第二類限制。

Output

一個正整數(shù)，表示集合{Xi}大小的最大值。

如果無解輸出NIE。

Sample Input

4 2 2

1 2

3 4

1 4

3 1

Sample Output

3

HINT

X3=1, X1=X4=2, X2=3

這樣答案為3。容易發(fā)現(xiàn)沒有更大的方案。

?

很容易發(fā)現(xiàn)這是差分約束系統(tǒng),若為操作1,$u\to v \quad w=1,v\to u\quad w=-1$。

若為操作2,$v\to u \quad w=0$。

然后我們考慮如何統(tǒng)計答案。如果一個環(huán)是正環(huán),那么一定不存在答案。

否則我們將圖縮點,一個$scc$中最大答案就是其中最長的最短路+1。

1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #include <numeric> 6 using namespace std; 7 #define maxn 601 8 #define INF 0x3f3f3f3f 9 inline int read() 10 { 11 int s=0,f=1; 12 char ch=getchar(); 13 while(ch<'0'||ch>'9') 14 { 15 if(ch=='-') 16 f=-1; 17 ch=getchar(); 18 } 19 while(ch>='0'&&ch<='9') 20 s=s*10+ch-'0',ch=getchar(); 21 return s*f; 22 } 23 int n,m1,m2; 24 int g[maxn][maxn]; 25 int f[maxn][maxn]; 26 int q[maxn],top,dfn[maxn],belong[maxn],low[maxn]; 27 int scc_dfn,scc_cnt,scc_size[maxn]; 28 bool inq[maxn]; 29 void tarjan(int u) 30 { 31 q[++top]=u; 32 inq[u]=true; 33 low[u]=dfn[u]=++scc_dfn; 34 for(int i=1;i<=n;i++) 35 { 36 if(i!=u&&f[u][i]) 37 { 38 if(!dfn[i]) 39 { 40 tarjan(i); 41 low[u]=min(low[i],low[u]); 42 } 43 else 44 if(inq[i]) 45 low[u]=min(low[u],dfn[i]); 46 } 47 } 48 if(dfn[u]==low[u]) 49 { 50 int v=-1; 51 ++scc_cnt; 52 while(v!=u) 53 { 54 v=q[top--]; 55 inq[v]=false; 56 belong[v]=scc_cnt; 57 } 58 } 59 } 60 int ans[maxn]; 61 int main() 62 { 63 n=read(); 64 m1=read(); 65 m2=read(); 66 int u,v; 67 memset(g,0x3f,sizeof(g)); 68 for(int i=1;i<=n;i++) 69 g[i][i]=0; 70 for(int i=1;i<=m1;i++) 71 { 72 u=read(); 73 v=read(); 74 g[u][v]=min(g[u][v],1); 75 g[v][u]=min(g[v][u],-1); 76 f[u][v]=f[v][u]=1; 77 } 78 for(int i=1;i<=m2;i++) 79 { 80 u=read(); 81 v=read(); 82 g[v][u]=min(g[v][u],0); 83 f[v][u]=1; 84 } 85 for(int k=1;k<=n;k++) 86 for(int i=1;i<=n;i++) 87 if(g[i][k]!=INF) 88 for(int j=1;j<=n;j++) 89 if(g[k][j]!=INF) 90 g[i][j]=min(g[i][j],g[i][k]+g[k][j]); 91 for(int i=1;i<=n;i++) 92 if(g[i][i]<0) 93 { 94 puts("NIE"); 95 exit(0); 96 } 97 for(int i=1;i<=n;i++) 98 if(!dfn[i]) 99 tarjan(i); 100 fill(ans+1,ans+scc_cnt+1,1); 101 for(int i=1;i<=n;i++) 102 for(int j=1;j<=n;j++) 103 if(belong[i]==belong[j]&&i!=j) 104 ans[belong[i]]=max(ans[belong[i]],g[i][j]+1); 105 printf("%d",accumulate(ans+1,ans+scc_cnt+1,0)); 106 } BZOJ 2788

轉(zhuǎn)載于:https://www.cnblogs.com/radioteletscope/p/7582589.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2788[Poi2012]Festival的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。