又一版2-SAT

总结：挑战程序设计上的2-SAT算法步骤模板不如自己写的快！！！

POJ2723：

题目链接：https://vjudge.net/problem/POJ-2723

题目意思：m道门，每道门两把锁，有n对钥匙，对应2*n把锁，已知一对钥匙内取出一把另一把就会消失，求按顺序最多可开多少门。

题目思路：钥匙和门是可重叠的关系，二分门的数量。

  1 #include<cstdio>
  2 #include<string.h>
  3 #include<vector>
  4 using namespace std;
  5 const int  N = 100005;
  6 vector<int>G[N];
  7 int dfn[N],low[N],vis[N],sta[N],scc[N],deny[N],a[N],b[N];
  8 int tot,cnt,top,num;
  9 int n,m;
 10 inline void init(){
 11     for(int i = 0;i < (n<<1);i ++){
 12         dfn[i] = low[i] = vis[i] = scc[i] = 0;
 13         G[i].clear();
 14     }
 15     tot = top = cnt = num = 0;
 16 }
 17 void add(int u,int v){
 18     G[u].push_back(v);
 19 }
 20 void tarjan(int u){
 21     dfn[u] = low[u] = ++cnt;
 22     vis[u] = 1;
 23     sta[top++] = u;
 24     for(int i = 0;i < G[u].size(); i++){
 25         int v = G[u][i];
 26         if(!dfn[v]){
 27             tarjan(v);
 28             low[u] = min(low[u],low[v]);
 29         }
 30         else if(vis[v])
 31             low[u] = min(low[u],dfn[v]);
 32     }
 33     if(dfn[u] == low[u]){
 34         int t;
 35         num++;
 36         do{
 37             t = sta[--top];
 38             vis[t] = 0;
 39             scc[t] = num;
 40         }while(t != u);
 41     }
 42 }
 43 bool ok(){
 44     for(int i = 0;i < (n<<1);i ++){
 45         if(!dfn[i]) 
 46             tarjan(i);
 47     }
 48 //    for(int i = 0;i < (n<<1);i ++){
 49 //        printf("scc = %d
",scc[i]);
 50 //    }
 51     for(int i = 0;i < (n<<1);i ++){
 52         if(scc[i] == scc[deny[i]]) 
 53             return false;
 54     }
 55     return true;
 56 }
 57 int solve(){
 58     int l = 0,r = m,mid;
 59     while(l < r){
 60         mid = (l+r)/2;
 61 //        for(int i = 0;i < (n<<1);i ++){
 62 //            G[i].clear();
 63 //        }
 64         init();
 65         for(int i = 0;i <= mid;i ++){
 66             add(deny[a[i]],b[i]);
 67             add(deny[b[i]],a[i]);
 68         }
 69 //        printf("*****mid = %d:
",mid);
 70         if(ok()) l = mid + 1;
 71         else r = mid;
 72     }
 73     return l;
 74 }
 75 int main(){
 76     while(scanf("%d%d",&n,&m)!=EOF){
 77         init();
 78         if(!n&&!m) return 0;
 79         for(int i = 0;i < n;i ++){
 80             int u,v;
 81             scanf("%d%d",&u,&v);
 82             deny[u] = v;
 83             deny[v] = u;
 84         } 
 85         for(int j = 0;j < m;j ++){
 86             scanf("%d%d",&a[j],&b[j]);
 87         }
 88         printf("%d
",solve()); 
 89     }
 90     return 0;
 91 }
 92 /*
 93 3 6
 94 0 3
 95 1 2
 96 4 5
 97 0 1
 98 0 2
 99 4 1
100 4 2
101 3 5
102 2 2
103 0 0
104 */

View Code

POJ2749：

题目链接：https://vjudge.net/problem/POJ-2749

题目意思：有 n 个农场，2个中转站，每个农场只能连接到一个中转站，2个农场可能不愿意连接到同一中转站，也可能只愿意连接到同一中转站，给出农场和中转站的坐标，求使得任意两个农场通过中转站连接的距离最大值最小，如果存在农场无法连接输出-1。

题目思路：要注意的是，2-SAT算法中（Tarjan算法中scc的编号即为反向拓扑序）根据每对顶点选出来拓扑序大的只是其中一种可行解，但是在本题中并不能保证一定是最优解（即无法包含所有情况（任意两站距离最小的情况））。所以只能二分最大距离。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<vector>
  6 using namespace std;
  7 typedef long long ll;
  8 
  9 const int INF = 1e9;
 10 const int MAXN = 3e3 + 5;
 11 int vis[MAXN], flag[MAXN];
 12 vector<int> G[MAXN], rG[MAXN];
 13 vector<int> vs;
 14 int n, m;
 15 void addedge(int x, int y)
 16 {
 17     G[x].push_back(y);
 18     rG[y].push_back(x);
 19 }
 20 
 21 void dfs(int u)
 22 {
 23     vis[u] = 1;
 24     for(int i = 0; i < G[u].size(); i++)
 25     {
 26         int v = G[u][i];
 27         if(!vis[v]) dfs(v);
 28     }
 29     vs.push_back(u);
 30 }
 31 
 32 void rdfs(int u, int k)
 33 {
 34     vis[u] = 1; flag[u] = k;
 35     for(int i = 0; i < rG[u].size(); i++)
 36     {
 37         int v = rG[u][i];
 38         if(!vis[v]) rdfs(v, k);
 39     }
 40 }
 41 
 42 int scc()
 43 {
 44     vs.clear();
 45     memset(vis, 0, sizeof vis);
 46     for(int i = 0; i < n; i++)
 47         if(!vis[i]) dfs(i);
 48     memset(vis, 0, sizeof vis);
 49     int k = 0;
 50     for(int i = vs.size() - 1; i >= 0; i--)
 51         if(!vis[vs[i]]) rdfs(vs[i], k++);
 52     return k;
 53 }
 54 
 55 bool judge()
 56 {
 57     int N = n;
 58     n = 2 * n;
 59     scc();
 60     n /= 2;
 61     for(int i = 0; i < n; i++)
 62         if(flag[i] == flag[i + N]) return false;
 63     return true;
 64 }
 65 int A, B, sx1, sy1, sx2, sy2;
 66 int hate1[MAXN], hate2[MAXN];
 67 int like1[MAXN], like2[MAXN];
 68 int px[MAXN], py[MAXN];
 69 void solve()
 70 {
 71     int l = 0, r = 4000000, mid;
 72     int DIST = abs(sx1 - sx2) + abs(sy1 - sy2);
 73     while(l < r)
 74     {
 75         mid = (l + r) / 2;
 76         for(int i = 0; i < 2 * n; i++)
 77         {
 78             G[i].clear(); rG[i].clear();
 79         }
 80         for(int i = 0; i < A; i++) // x xor y = 1
 81         {
 82             addedge(hate1[i], hate2[i] + n);
 83             addedge(hate1[i] + n, hate2[i]);
 84             addedge(hate2[i], hate1[i] + n);
 85             addedge(hate2[i] + n, hate1[i]);
 86         }
 87         for(int i = 0; i < B; i++) // x xor y = 0
 88         {
 89             addedge(like1[i], like2[i]);
 90             addedge(like1[i] + n, like2[i] + n);
 91             addedge(like2[i], like1[i]);
 92             addedge(like2[i] + n, like1[i] + n);
 93         }
 94         for(int i = 0; i < n; i++)
 95         {
 96             for(int j = 0; j < i; j++)
 97             {
 98                 // 连接到同一中转站
 99                 if(abs(px[i] - sx1) + abs(py[i] - sy1) + abs(px[j] - sx1) + abs(py[j] - sy1) > mid)
100                 {
101                     addedge(i, j + n); addedge(j, i + n);
102                 }
103                 if(abs(px[i] - sx2) + abs(py[i] - sy2) + abs(px[j] - sx2) + abs(py[j] - sy2) > mid)
104                 {
105                     addedge(i + n, j); addedge(j + n, i);
106                 }
107                 // 连接到不同中转站
108                 if(abs(px[i] - sx1) + abs(py[i] - sy1) + abs(px[j] - sx2) + abs(py[j] - sy2) + DIST > mid)
109                 {
110                     addedge(i, j); addedge(j + n, i + n);
111                 }
112                 if(abs(px[j] - sx1) + abs(py[j] - sy1) + abs(px[i] - sx2) + abs(py[i] - sy2) + DIST > mid)
113                 {
114                     addedge(j, i); addedge(i + n, j + n);
115                 }
116             }
117         }
118         if(!judge()) l = mid + 1;
119         else r = mid;
120     }
121     if(l == 0 || l == 4000000) puts("-1");
122     else printf("%d
", l);
123 }
124 int main()
125 {
126     while(~scanf("%d%d%d", &n, &A, &B))
127     {
128         scanf("%d%d%d%d", &sx1, &sy1, &sx2, &sy2);
129         for(int i = 0; i < n; i++) scanf("%d%d", &px[i], &py[i]);
130         for(int i = 0; i < A; i++)
131         {
132             scanf("%d%d", &hate1[i], &hate2[i]);
133             hate1[i]--; hate2[i]--;
134         }
135         for(int i = 0; i < B; i++)
136         {
137             scanf("%d%d", &like1[i], &like2[i]);
138             like1[i]--; like2[i]--;
139         }
140         solve();
141     }
142     return 0;
143 }

View Code

洛谷P3209：

题目链接：https://www.luogu.com.cn/problem/P3209

题目意思：若能将无向图G=(V,E)画在平面上使得任意两条无重合顶点的边不相交，则称G是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。判断所给图是否是平面图。

题目思路：平面图定理 + 以哈密顿通路为圆判断边的2-SAT关系。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 const int maxn=2e3+1e1;
  7 
  8 int x[maxn<<4],y[maxn<<4],vis[maxn<<4];
  9 int id[maxn];
 10 int fa[maxn<<5];
 11 int T,n,m;
 12 
 13 inline int findfa(int x)
 14 {
 15     return fa[x] == x ? x : fa[x] = findfa(fa[x]);
 16 }
 17 
 18 inline void initfa()
 19 {
 20     for(int i=1;i<=m<<1;i++)
 21         fa[i] = i;
 22 }
 23 
 24 inline bool cross(int x1,int x2,int y1,int y2)
 25 {
 26     if( x1 == x2 || y1 == y2 || x1 == y2 || x2 == y1 )
 27         return 0;
 28     if( x1 < x2 && y1 < y2 && x2 < y1 )
 29         return 1;
 30     if( x2 < x1 && y2 < y1 && x1 < y2 )
 31         return 1;
 32     return 0;
 33 }
 34 
 35 inline bool check()
 36 {
 37     initfa();
 38     for(int i=1;i<=m;i++)
 39     {
 40         if( vis[i] )
 41             continue;
 42         for(int j=1;j<=m;j++)
 43         {
 44             if( vis[j] )
 45                 continue;
 46             if( !cross(x[i],x[j],y[i],y[j]) )
 47                 continue;
 48             int fai = findfa(i) , faj = findfa(j);
 49             if( fai == faj )
 50                 return 0;
 51             fa[fai] = findfa( j + m ),
 52             fa[faj] = findfa( i + m );
 53         }
 54     }
 55     return 1;
 56 }
 57 
 58 inline void init()
 59 {
 60     memset(x,0,sizeof(x));
 61     memset(y,0,sizeof(y));
 62     memset(vis,0,sizeof(vis));
 63     n = m = 0;
 64 }
 65 
 66 inline int getint()
 67 {
 68     int ret = 0;
 69     char ch = getchar();
 70     while( ch < '0' || ch > '9' )
 71         ch = getchar();
 72     while( '0' <= ch && ch <= '9' )
 73         ret = ret * 10 + ( ch - '0' ),
 74         ch = getchar();
 75     return ret;
 76 }
 77 int main()
 78 {
 79     T = getint();
 80 
 81     while( T-- )
 82     {
 83         init();
 84         n = getint() , m = getint();
 85         for(int i=1;i<=m;i++)
 86             x[i] = getint() , y[i] = getint();
 87         for(int i=1;i<=n;i++)
 88             id[getint()] = i;
 89         if( m > 3 * n + 6 )
 90         {
 91             puts("NO");
 92             continue;
 93         }
 94         for(int i=1,a,b;i<=m;i++)
 95         {
 96             a = id[x[i]] , b = id[y[i]];
 97             x[i] = min( a , b ),
 98             y[i] = max( a , b );
 99         }
100         for(int i=1;i<=m;i++)
101             if( y[i] == x[i] + 1 || ( y[i]==n && x[i]==0) )
102                 vis[i] = 1;
103         if( check() )
104             puts("YES");
105         else puts("NO");
106     }
107     return 0;
108 }

View Code