CSES 1684 - Giant Pizza 解題心得( 題目 )
解題概念:2-SAT
解題方法:這題是一個要二選一的問題，也就是2-SAT，我們可以把選項與選項之間畫成圖，之後透過SCC(強連通分量)的技巧判斷是否有解、以及可以縮點，有解的話在之後被SCC壓過後的DAG也可以使用topu來找解。
//Author:En Chi Tsung(欉恩祁)
//Date:2022/03/27
import java.util.*;
import java.io.*;
public class cses1684{
public static ArrayList<ArrayList<Integer>> e=new ArrayList<>();
public static ArrayList<ArrayList<Integer>> scce=new ArrayList<>();
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int rd,ret,m,cnt,t,no,o;
public static int[] scc=new int[200005];
public static int[] dfs=new int[200005];
public static int[] low=new int[200005];
public static boolean[] vis=new boolean[200005];
public static boolean[] ins=new boolean[200005];
public static Stack<Integer> st=new Stack<>();
public static void main(String[] args) throws Exception{
final int n=readint();
m=readint();
int x,y,a,b;
boolean ans=true;
for(int i=0;i<=m*2;i++) {
e.add(new ArrayList<>());
scce.add(new ArrayList<>());
}
for(int i=0;i<n;i++) {
x=readint();
a=readint();
y=readint();
b=readint();
if(x=='+') {
a+=m;
}
if(y=='+') {
b+=m;
}
e.get(rev(a)).add(b);
e.get(rev(b)).add(a);
}
for(int i=1;i<=2*m;i++) {
if(!vis[i]) {
tarjan(i);
}
}
for(int i=1;i<=m;i++) {;
if(scc[i]==scc[i+m]) {
ans=false;
break;
}
}
if(!ans) {
System.out.println("IMPOSSIBLE");
}
else {
find();
}
}
public static int rev(int x) {
if(x>m)return x-m;
return x+m;
}
public static void find() throws Exception{
int[] out=new int[no];
int[] ans=new int[no];
int[] opp=new int[no];
Queue<Integer> q=new LinkedList<>();
int o;
for(int i=1;i<e.size();i++) {
for(int j:e.get(i)) {
if(scc[i]==scc[j]) continue;
scce.get(scc[j]).add(scc[i]);
out[scc[i]]++;
}
}
for(int i=1;i<=m;i++) {
opp[scc[i]]=scc[i+m];
}
for(int i=m+1;i<=2*m;i++) {
opp[scc[i]]=scc[i-m];
}
Arrays.fill(ans,-1);
for(int i=0;i<no;i++) {
if(out[i]==0) {
q.offer(i);
while(!q.isEmpty()) {
o=q.poll();
for(int j:scce.get(o)) {
out[j]--;
if(out[j]==0) {
out[j]=-1;
q.offer(j);
}
}
if(ans[o]==-1) {
ans[o]=1;
ans[opp[o]]=0;
}
}
}
}
for(int i=1;i<=m;i++) {
bw.write((ans[scc[i]]==0)?"+ ":"- ");
}
bw.write("\n");
bw.flush();
}
public static void tarjan(int x) {
dfs[x]=low[x]=t++;
vis[x]=ins[x]=true;;
st.push(x);
for(int i:e.get(x)) {
if(!vis[i]) {
tarjan(i);
low[x]=Math.min(low[x],low[i]);
}
else if(ins[i]) {
low[x]=Math.min(low[x],dfs[i]);
}
}
if(!ins[x])return;
if(dfs[x]==low[x]) {
while(true) {
o=st.pop();
ins[o]=false;
scc[o]=no;
if(o==x)break;
}
no++;
}
ins[x]=false;
}
public static int readint() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
if(ret==0) {
br.read();
return rd;
}
return ret;
}
}
文章標籤
全站熱搜
留言列表
