【bzoj 3495】PA2010 Riddle
Description
有n個城鎮被分成了k個郡，有m條連接城鎮的無向邊。要求給每個郡選擇一個城鎮作為首都，滿足每條邊至少有一個端點是首都。
Input
第一行有三個整數，城鎮數n（1<=n<=10^6），邊數m（0<=m<=10^6），郡數k（1<=k<=n）。
接下來m行，每行有兩個整數ai和bi（ai≠bi），表示有一條無向邊連接城鎮ai和bi。
接下來k行，第j行以一個整數wj開頭，后面是wj個整數，表示第j個郡包含的城鎮。
Output
若有解輸出TAK，否則輸出NIE。
每個點 $x$ 拆成兩對點，$x$ 代表選擇 $x$ 為首都，$x+n$ 表示不選擇 $x$ 為首都，$x+2n$ 表示 $x$ 的前綴已包含首都，$x+3n$表示 $x$ 的前綴不包含首都。
對于每一條原圖中無向邊 $(x,y)$ ，因為至少有一個端點為首都，連邊 $(x+n,y)$ ，$(y+n,x)$。
對于每一個點 $x$ ，連邊 $(x,x+2n)$ ，$(x+3n,x+n)$。
對于每一個點 $x$ 與它的上一個點 $last$ ，連邊方式如下：$(last+2n,x+2n)$，$(x+3n,last+3n)$，$(last+2n,x+n)$，$(x,last+3n)$。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define LL long long 5 using namespace std; 6 const int N=4e6+5; 7 int n,m,k,cnt,x,y,last,tim,top,color; 8 int first[N],dfn[N],low[N],sta[N],c[N]; 9 bool vis[N]; 10 struct edge{int to,next;}e[N*3]; 11 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;} 12 int read() 13 { 14 int x=0,f=1;char c=getchar(); 15 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 16 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 17 return x*f; 18 } 19 void tarjan(int x) 20 { 21 low[x]=dfn[x]=++tim; 22 sta[++top]=x;vis[x]=true; 23 for(int i=first[x];i;i=e[i].next) 24 { 25 int to=e[i].to; 26 if(!dfn[to])tarjan(to),low[x]=min(low[x],low[to]=min(low[x],low[to])); 27 else if(vis[to])low[x]=min(low[x],dfn[to]); 28 } 29 if(low[x]==dfn[x]) 30 { 31 color++; 32 while(sta[top]!=x)vis[sta[top]]=false,c[sta[top--]]=color; 33 vis[x]=false;c[x]=color;top--; 34 } 35 } 36 bool check() 37 { 38 for(int i=1;i<=n;i++) 39 if(c[i]==c[i+n]||c[i+2*n]==c[i+3*n])return false; 40 return true; 41 } 42 int main() 43 { 44 n=read();m=read();k=read(); 45 for(int i=1;i<=m;i++) 46 { 47 x=read();y=read(); 48 ins(x+n,y);ins(y+n,x); 49 } 50 for(int i=1;i<=k;i++) 51 { 52 x=read();last=0; 53 for(int j=1;j<=x;j++) 54 { 55 y=read(); 56 ins(y,y+2*n);ins(y+3*n,y+n); 57 if(last) 58 { 59 ins(last+2*n,y+2*n); 60 ins(y+3*n,last+3*n); 61 ins(last+2*n,y+n); 62 ins(y,last+3*n); 63 } 64 last=y; 65 } 66 } 67 for(int i=1;i<=4*n;i++)if(!dfn[i])tarjan(i); 68 if(check())printf("TAK"); 69 else printf("NIE"); 70 return 0; 71 }
浙公網安備 33010602011771號