[关闭]
@ivorysi 2018-01-02T08:26:08.000000Z 字数 23410 阅读 764

图论学习笔记

笔记

tarjan

POJ 1523 The Cow Prom

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2364 Accepted: 1393

Description

The N (2 <= N <= 10,000) cows are so excited: it's prom night! They are dressed in their finest gowns, complete with corsages and new shoes. They know that tonight they will each try to perform the Round Dance.
Only cows can perform the Round Dance which requires a set of ropes and a circular stock tank. To begin, the cows line up around a circular stock tank and number themselves in clockwise order consecutively from 1..N. Each cow faces the tank so she can see the other dancers.
They then acquire a total of M (2 <= M <= 50,000) ropes all of which are distributed to the cows who hold them in their hooves. Each cow hopes to be given one or more ropes to hold in both her left and right hooves; some cows might be disappointed.
For the Round Dance to succeed for any given cow (say, Bessie), the ropes that she holds must be configured just right. To know if Bessie's dance is successful, one must examine the set of cows holding the other ends of her ropes (if she has any), along with the cows holding the other ends of any ropes they hold, etc. When Bessie dances clockwise around the tank, she must instantly pull all the other cows in her group around clockwise, too. Likewise,
if she dances the other way, she must instantly pull the entire group counterclockwise (anti-clockwise in British English).
Of course, if the ropes are not properly distributed then a set of cows might not form a proper dance group and thus can not succeed at the Round Dance. One way this happens is when only one rope connects two cows. One cow could pull the other in one direction, but could not pull the other direction (since pushing ropes is well-known to be fruitless). Note that the cows must Dance in lock-step: a dangling cow (perhaps with just one rope) that is eventually pulled along disqualifies a group from properly performing the Round Dance since she is not immediately pulled into lockstep with the rest.
Given the ropes and their distribution to cows, how many groups of cows can properly perform the Round Dance? Note that a set of ropes and cows might wrap many times around the stock tank.

Input

Line 1: Two space-separated integers: N and M
Lines 2..M+1: Each line contains two space-separated integers A and B that describe a rope from cow A to cow B in the clockwise direction.

Output

Line 1: A single line with a single integer that is the number of groups successfully dancing the Round Dance.

Sample Input

5 4
2 4
3 5
1 2
4 1

Sample Output

1

Hint

Explanation of the sample:
ASCII art for Round Dancing is challenging. Nevertheless, here is a representation of the cows around the stock tank:

  1.        _1___
  3.       /**** \
  5.    5 /****** 2
  7.   / /**TANK**|
  9.   \ \********/
  11.    \ \******/  3
  13.     \ 4____/  /
  15.      \_______/

Cows 1, 2, and 4 are properly connected and form a complete Round Dance group. Cows 3 and 5 don't have the second rope they'd need to be able to pull both ways, thus they can not properly perform the Round Dance.

题解

因为强连通分量（两个以上）至少有一个环，所以搜有一个点以上的强连通分量就好了

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 100005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. struct node {
  29.     int to,next;
  30. }edge[MAXN*5];
  31. int head[MAXN],sumedge;
  32. int n,m;
  33. int dfn[MAXN],low[MAXN],instack[MAXN],inx,tot;
  34. stack<int> st;
  35. void tarjan(int u) {
  36.     dfn[u]=low[u]=++inx;
  37.     st.push(u);
  38.     instack[u]=1;
  39.     for(int i=head[u];i;i=edge[i].next) {
  40.     int v=edge[i].to;
  41.     if(!dfn[v]) {
  42.         tarjan(v);
  43.         low[u]=min(low[v],low[u]);
  44.     }
  45.     else if(instack[v]==1) {
  46.         low[u]=min(dfn[v],low[u]);
  47.     }
  48.     }
  49.     if(low[u]==dfn[u]) {
  50.     ++tot;
  51.     int cnt=0;
  52.     while(1) {
  53.         int x=st.top();st.pop();
  54.         ++cnt;
  55.         instack[x]=2;
  56.         if(x==u) break; 
  57.     }
  58.     if(cnt==1) --tot;
  59.     }
  60. }
  61. void add(int u,int v) {
  62.     edge[++sumedge].to=v;
  63.     edge[sumedge].next=head[u];
  64.     head[u]=sumedge;
  65. }
  66. void solve() {
  67.     n=read();
  68.     m=read();
  69.     int u,v;
  70.     siji(i,1,m) {
  71.     u=read();
  72.     v=read();
  73.     add(u,v);
  74.     }
  75.     siji(i,1,n) {
  76.     if(!dfn[i]) tarjan(i);
  77.     }
  78.     printf("%d\n",tot);
  79. }
  80. int main() {
  81. #ifdef ivorysi
  82.     freopen("f1.in","r",stdin);
  83. #endif
  84.     solve();
  85. }

POJ 2942 Network of Schools

Description

A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.

Input

The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

Output

Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

Sample Input

5
2 4 3 0
4 5 0
0
0
1 0

Sample Output

1
2

Source

IOI 1996

题解

子任务A比较简单，就是tarjan缩点后入度为0的点
B的话是入度为0和出度为0的点取个max
因为每个出度向某一个走不到入度连一条边（如果每一个入度都能走到就任意连），然后多余的入度都连到某个出度上即可

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 100005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. struct node {
  29.     int to,next;
  30. }edge[MAXN*5];
  31. int head[MAXN],sumedge;
  32. int n,m;
  33. int dfn[MAXN],low[MAXN],instack[MAXN],inx,tot,col[MAXN],ind[MAXN],outd[MAXN];
  34. stack<int> st;
  35. void tarjan(int u) {
  36.     dfn[u]=low[u]=++inx;
  37.     st.push(u);
  38.     instack[u]=1;
  39.     for(int i=head[u];i;i=edge[i].next) {
  40.     int v=edge[i].to;
  41.     if(!dfn[v]) {
  42.         tarjan(v);
  43.         low[u]=min(low[v],low[u]);
  44.     }
  45.     else if(instack[v]==1) {
  46.         low[u]=min(dfn[v],low[u]);
  47.     }
  48.     }
  49.     if(low[u]==dfn[u]) {
  50.     ++tot;
  51.     while(1) {
  52.         int x=st.top();st.pop();
  53.         col[x]=tot;
  54.         instack[x]=2;
  55.         if(x==u) break; 
  56.     }
  57.     }
  58. }
  59. void add(int u,int v) {
  60.     edge[++sumedge].to=v;
  61.     edge[sumedge].next=head[u];
  62.     head[u]=sumedge;
  63. }
  64. void solve() {
  65.     n=read();
  66.     int u;
  67.     siji(i,1,n) {
  68.     u=read();
  69.     while(u!=0) {
  70.         add(i,u);
  71.         u=read();
  72.     }
  73.     }
  74.     siji(i,1,n) {
  75.     if(!dfn[i]) tarjan(i);
  76.     }
  77.     siji(i,1,n) {
  78.     for(int j=head[i];j;j=edge[j].next) {
  79.         int v=edge[j].to;
  80.         if(col[v]!=col[i]) {
  81.         ind[col[v]]++;
  82.         outd[col[i]]++;
  83.         }
  84.     }
  85.     }
  86.     if(tot==1) {
  87.     puts("1");puts("0");
  88.     return;
  89.     }
  90.     int ans1=0,ans2=0;
  91.     siji(i,1,tot) {
  92.     if(ind[i]==0) ans1++;
  93.     if(outd[i]==0) ans2++;
  94.     }
  95.     ans2=max(ans1,ans2);
  96.     printf("%d\n%d\n",ans1,ans2);
  97. }
  98. int main() {
  99. #ifdef ivorysi
  100.     freopen("f1.in","r",stdin);
  101. #endif
  102.     solve();
  103. }

POJ 1523 SPF

Description

Consider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, 3, in the network on the left would prevent some of the still available nodes from communicating with each other. Nodes 1 and 2 could still communicate with each other as could nodes 4 and 5, but communication between any other pairs of nodes would no longer be possible.
Node 3 is therefore a Single Point of Failure (SPF) for this network. Strictly, an SPF will be defined as any node that, if unavailable, would prevent at least one pair of available nodes from being able to communicate on what was previously a fully connected network. Note that the network on the right has no such node; there is no SPF in the network. At least two machines must fail before there are any pairs of available nodes which cannot communicate.

Input

The input will contain the description of several networks. A network description will consist of pairs of integers, one pair per line, that identify connected nodes. Ordering of the pairs is irrelevant; 1 2 and 2 1 specify the same connection. All node numbers will range from 1 to 1000. A line containing a single zero ends the list of connected nodes. An empty network description flags the end of the input. Blank lines in the input file should be ignored.

Output

For each network in the input, you will output its number in the file, followed by a list of any SPF nodes that exist.
The first network in the file should be identified as "Network #1", the second as "Network #2", etc. For each SPF node, output a line, formatted as shown in the examples below, that identifies the node and the number of fully connected subnets that remain when that node fails. If the network has no SPF nodes, simply output the text "No SPF nodes" instead of a list of SPF nodes.

Sample Input

1 2
5 4
3 1
3 2
3 4
3 5
0
1 2
2 3
3 4
4 5
5 1
0
1 2
2 3
3 4
4 6
6 3
2 5
5 1
0
0

Sample Output

Network #1
SPF node 3 leaves 2 subnets
Network #2
No SPF nodes
Network #3
SPF node 2 leaves 2 subnets
SPF node 3 leaves 2 subnets

题解

这道题在求割点的时候一并求了它把图分成几个块就行
就是low[v]>=dfn[u]出现的次数

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 100005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. struct node {
  29.     int to,next;
  30. }edge[MAXN*5];
  31. int head[MAXN],sumedge;
  32. int n,m;
  33. int dfn[MAXN],low[MAXN],cnt[MAXN],inx;
  34. bool is_AP[MAXN];
  35. void tarjan(int u,int fa) {
  36.     dfn[u]=low[u]=++inx;
  37.     int son=0;
  38.     for(int i=head[u];i;i=edge[i].next) {
  39.     int v=edge[i].to;
  40.     if(!dfn[v]) {
  41.         tarjan(v,u);
  42.         ++son;
  43.         low[u]=min(low[u],low[v]);
  44.         if(fa!=0 && low[v]>=dfn[u]) {
  45.         is_AP[u]=1;
  46.         cnt[u]++;
  47.         }
  48.     }
  49.     else if(v!=fa){
  50.         low[u]=min(dfn[v],low[u]);
  51.     }
  52.     }
  53.     if(fa!=0 && is_AP[u]) ++cnt[u];
  54.     if(fa==0 && son>1) is_AP[u]=1,cnt[u]=son;
  55. }
  56. void add(int u,int v) {
  57.     edge[++sumedge].to=v;
  58.     edge[sumedge].next=head[u];
  59.     head[u]=sumedge;
  60. }
  61. void addtwo(int u,int v) {
  62.     add(u,v);add(v,u);
  63. }
  64. int main() {
  65. #ifdef ivorysi
  66.     freopen("f1.in","r",stdin);
  67. #endif
  68.     int u,v,n;
  69.     int t=0;
  70.     while(1) {
  71.     ++t;
  72.     n=0;
  74.     memset(head,0,sizeof(head));
  75.     sumedge=0;
  76.     memset(dfn,0,sizeof(dfn));
  77.     memset(low,0,sizeof(low));
  78.     memset(is_AP,0,sizeof(is_AP));
  79.     memset(cnt,0,sizeof(cnt));
  80.     inx=0;
  81.     scanf("%d",&u);
  82.     if(u==0) break;
  83.     while(u!=0) {
  84.         scanf("%d",&v);
  85.         n=max(n,u);
  86.         n=max(n,v);
  87.         addtwo(u,v);
  88.         scanf("%d",&u);
  89.     }
  90.     siji(i,1,n) {
  91.         if(!dfn[i]) tarjan(i,0);
  92.     }
  93.     printf("Network #%d\n",t);
  94.     bool flag=1;
  95.     siji(i,1,n) {
  96.         if(is_AP[i]) {
  97.         printf("  SPF node %d leaves %d subnets\n",i,cnt[i]);
  98.         flag=0;
  99.         }
  100.     }
  101.     if(flag) {
  102.         puts("  No SPF nodes");
  103.     }
  104.     puts("");
  105.     }
  106. }

POJ 2942 Knights of the Round Table

Description

Being a knight is a very attractive career: searching for the Holy Grail, saving damsels in distress, and drinking with the other knights are fun things to do. Therefore, it is not very surprising that in recent years the kingdom of King Arthur has experienced an unprecedented increase in the number of knights. There are so many knights now, that it is very rare that every Knight of the Round Table can come at the same time to Camelot and sit around the round table; usually only a small group of the knights isthere, while the rest are busy doing heroic deeds around the country.
Knights can easily get over-excited during discussions-especially after a couple of drinks. After some unfortunate accidents, King Arthur asked the famous wizard Merlin to make sure that in the future no fights break out between the knights. After studying the problem carefully, Merlin realized that the fights can only be prevented if the knights are seated according to the following two rules:
The knights should be seated such that two knights who hate each other should not be neighbors at the table. (Merlin has a list that says who hates whom.) The knights are sitting around a roundtable, thus every knight has exactly two neighbors.
An odd number of knights should sit around the table. This ensures that if the knights cannot agree on something, then they can settle the issue by voting. (If the number of knights is even, then itcan happen that yes" andno" have the same number of votes, and the argument goes on.)
Merlin will let the knights sit down only if these two rules are satisfied, otherwise he cancels the meeting. (If only one knight shows up, then the meeting is canceled as well, as one person cannot sit around a table.) Merlin realized that this means that there can be knights who cannot be part of any seating arrangements that respect these rules, and these knights will never be able to sit at the Round Table (one such case is if a knight hates every other knight, but there are many other possible reasons). If a knight cannot sit at the Round Table, then he cannot be a member of the Knights of the Round Table and must be expelled from the order. These knights have to be transferred to a less-prestigious order, such as the Knights of the Square Table, the Knights of the Octagonal Table, or the Knights of the Banana-Shaped Table. To help Merlin, you have to write a program that will determine the number of knights that must be expelled.

Input

The input contains several blocks of test cases. Each case begins with a line containing two integers 1 ≤ n ≤ 1000 and 1 ≤ m ≤ 1000000 . The number n is the number of knights. The next m lines describe which knight hates which knight. Each of these m lines contains two integers k1 and k2 , which means that knight number k1 and knight number k2 hate each other (the numbers k1 and k2 are between 1 and n ).
The input is terminated by a block with n = m = 0 .

Output

For each test case you have to output a single integer on a separate line: the number of knights that have to be expelled.

Sample Input

5 5
1 4
1 5
2 5
3 4
4 5
0 0

Sample Output

2

Hint

Huge input file, 'scanf' recommended to avoid TLE.

题解

这道题是一个非常厉害的题……总和了很多知识点
还让我发现了…原来我根本不会写双联通分量
首先憎恨关系这个很难处理，所以我们可以考虑，建一个反图，也就是非憎恨关系，我们将没有憎恨关系的人连边
然后跑一个双联通分量，这个双联通分量需要有奇数个点的环，也就是奇环，有了一个奇环保证了整个双联通分量的每个点都在一个奇环里，那么有奇环用什么判断，二分图染色，如果染色不成功，那么必然是合法的，否则这一整个双联通分量都不能要
那么我到底跪在哪里了呢，因为我双联通分量求错了，双联通分量需要一个栈，在low[v]>=dfn[u]的时候出去一个双联通分量，然而这个栈弹出的时候只能弹到v点，而不能从v点继续往下弹，因为u点可能还遍历过别的出边，这个出边指向的点还在栈里，如果弹到u这个出边指向的点就会被错误的弹出
例如这么一组数据

  1. 5 10
  2. 3 1
  3. 2 4
  4. 2 1
  5. 1 1
  6. 1 3
  7. 1 1
  8. 2 1
  9. 1 3
  10. 1 1
  11. 4 3
  12. 0 0

答案是0，但是极有可能，5先遍历到了4，然后弹出2 3 时为了找到5把4也弹出了
因为是多组数据所以栈要清一遍！！！！
QAQ
代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 2005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. struct node {
  29.     int to,next;
  30. }edge[MAXN*MAXN*2];
  31. int head[MAXN],sumedge;
  32. int n,m;
  33. int dfn[MAXN],low[MAXN],inx,col[MAXN],tot;
  34. int flag[MAXN],ans,st[MAXN],top;
  35. bool choose[MAXN],vis[MAXN][MAXN];
  36. vector<int> vi;
  37. bool dfs(int u) {
  38.     for(int i=head[u];i;i=edge[i].next) {
  39.     int v=edge[i].to;
  40.     if(col[v]==col[u]) {
  41.         if(!flag[v]) {
  42.         flag[v]=flag[u]^1;
  43.         if(!dfs(v)) return false;
  44.         }
  45.         else if(flag[u]==flag[v]){
  46.         return false;
  47.         }
  48.     }
  49.     }
  50.     return true;
  51. }
  52. void tarjan(int u) {
  53.     dfn[u]=low[u]=++inx;
  54.     st[++top]=u;
  55.     for(int i=head[u];i;i=edge[i].next) {
  56.     int v=edge[i].to;
  57.     if(!dfn[v]) {
  58.         tarjan(v);
  59.         low[u]=min(low[u],low[v]);
  60.         if(low[v]>=dfn[u]) {
  61.         vi.clear();
  62.         int cnt=0;
  63.         ++tot;
  64.         while(st[top+1]!=v) {
  65.             int x=st[top];
  66.             vi.push_back(x);
  67.             col[x]=tot;
  68.             --top;
  69.             ++cnt;
  70.         }
  71.         vi.push_back(u);
  72.         col[u]=tot;
  73.         ++cnt;
  74.         if(cnt<3) {
  75.             continue;
  76.         }
  77.         flag[u]=2;
  78.         if(!dfs(u)) {
  79.             xiaosiji(j,0,cnt) {
  80.             choose[vi[j]]=1;
  81.             }
  82.         }
  83.         col[u]=0;
  84.         flag[u]=0;
  85.         }
  86.     }
  87.     else{
  88.         low[u]=min(dfn[v],low[u]);
  89.     }
  90.     }
  91. }
  92. void add(int u,int v) {
  93.     edge[++sumedge].to=v;
  94.     edge[sumedge].next=head[u];
  95.     head[u]=sumedge;
  96. }
  97. void addtwo(int u,int v) {
  98.     add(u,v);add(v,u);
  99. }
  100. void solve() {
  101.     memset(head,0,sizeof(head));
  102.     sumedge=0;
  103.     memset(dfn,0,sizeof(dfn));
  104.     memset(low,0,sizeof(low));
  105.     inx=0;
  106.     memset(choose,0,sizeof(choose));
  107.     memset(vis,0,sizeof(vis));
  108.     memset(col,0,sizeof(col));
  109.     memset(flag,0,sizeof(flag));
  110.     ans=0;
  111.     tot=0;
  112.     int u,v;
  113.     siji(i,1,m) {
  114.     u=read();v=read();
  115.     vis[u][v]=1;
  116.     vis[v][u]=1;
  117.     }
  118.     siji(i,1,n) {
  119.     siji(j,i+1,n) {
  120.         if(!vis[i][j]) addtwo(i,j);
  121.     }
  122.     }
  123.     siji(i,1,n) {
  124.     top=0;
  125.     memset(st,0,sizeof(st));
  126.     if(!dfn[i]) tarjan(i);
  127.     }
  128.     siji(i,1,n) {
  129.     if(!choose[i]) ++ans;
  130.     }
  131.     printf("%d\n",ans);
  132. }
  133. int main() {
  134. #ifdef ivorysi
  135.     freopen("f1.in","r",stdin);
  136. #endif
  137.     while(1) {
  138.     n=read();m=read();
  139.     if(n==0 && m==0) break;
  140.     solve();
  141.     }
  143. }

　2-SAT

也就是对于有一些集合，每个集合里有两个元素，我们对于每个集合只能选一个，这些元素之间有一些对立关系
k-SAT是一个NP问题，而2-SAT有一些特殊的方法
我们对于四种常见模型可以采取以下的方法连边
思路是对每个元素都建一个点

（A,B）不能同时取

那么选了A必须选B'，选了B必须选A'
A->B' B->A'

（A,B）不能同时不取

那么选了A'必须选B，选了B'必须选A
A'->B B'->A

(A,B)要么都取，要么都不取

那么选了A'必须选B'，选了B'必须选A',选了A必须选B，选了B必须选A
A'->B' B'->A' A->B B->A

（A,A'）必须选A

A’->A
选了A'必须选A,保证了A拓扑序在前
解的多解依赖于拓扑序的多情况，这样的话去除了A'在A前面的情况
然后我们对于这些点跑tarjan，跑完之后缩点，缩点之后存反边，然后拓扑排序
但是这一步其实不必要，因为反边之后的拓扑序就是求tarjan时点编号的正序，这个问题就完美解决了
也就是说2-SAT就是——tarjan求强连通分量！

POJ 3678 Katu Puzzle

Description

Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 ≤ c ≤ 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 ≤ Xi ≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:
Xa op Xb = c
The calculating rules are:
AND 0 1
0 0 0
1 0 1
OR 0 1
0 0 1
1 1 1
XOR 0 1
0 0 1
1 1 0
Given a Katu Puzzle, your task is to determine whether it is solvable.

Input

The first line contains two integers N (1 ≤ N ≤ 1000) and M,(0 ≤ M ≤ 1,000,000) indicating the number of vertices and edges.
The following M lines contain three integers a (0 ≤ a < N), b(0 ≤ b < N), c and an operator op each, describing the edges.

Output

Output a line containing "YES" or "NO".

Sample Input

4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR

Sample Output

YES

Hint

X0 = 1, X1 = 1, X2 = 0, X3 = 1.

Source

题解

这道题的思路很明显
如果是AND 1
a的0 连到a的1
b的0连到b的1
a的1连到b的1
b的1连到a的1
如果AND 0
a的1连到b的0
b的1连到a的0

如果OR 1
a的0连到b的1
b的0连到a的1
如果OR 0
a的1连到a的0
b的1连到b的0
a的0连到b的0
b的0连到a的0

如果XOR 1
a的0连到b的1
a的1连到b的0
b的1连到a的0
b的0连到a的1

如果XOR 0
a的0连到b的0
b的0连到a的0
a的1连到b的1
b的1连到a的1

然而我这个傻逼……tarjan写错了！！！！！

题解

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 10005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. struct node {
  29.     int to,next;
  30. }edge[4000005];
  31. int head[MAXN*2],sumedge;
  32. int n,m;
  33. int dfn[MAXN*2],low[MAXN*2],inx,instack[MAXN*2],col[MAXN*2],tot;
  34. stack<int> st;
  35. void add(int u,int v) {
  36.     edge[++sumedge].to=v;
  37.     edge[sumedge].next=head[u];
  38.     head[u]=sumedge;
  39. }
  40. void addtwo(int u,int v) {
  41.     add(u,v);add(v,u);
  42. }
  43. void tarjan(int u) {
  44.     dfn[u]=low[u]=++inx;
  45.     st.push(u);
  46.     instack[u]=1;
  47.     for(int i=head[u];i;i=edge[i].next) {
  48.     int v=edge[i].to;
  49.     if(!dfn[v]) {
  50.         tarjan(v);
  51.         low[u]=min(low[u],low[v]);
  52.     }
  53.     else if(instack[v]==1) {
  54.         low[u]=min(dfn[v],low[u]);
  55.     }
  56.     }
  57.     if(low[u]==dfn[u]) {
  58.     ++tot;
  59.     int x;
  60.     while(1) {
  61.         x=st.top();st.pop();
  62.         col[x]=tot;
  63.         instack[x]=2;
  64.         if(x==u) break;
  65.     }
  66.     }
  67. }
  68. void solve() {
  69.     n=read();m=read();
  70.     int a,b,c;
  71.     char op[10];
  72.     siji(i,1,m) {
  73.     scanf("%d%d%d",&a,&b,&c);;
  74.     scanf("%s",op+1);
  75.     ++a;++b;
  76.     if(op[1]=='A') {
  77.         if(c==1) {//must choose 1
  78.         add(a*2-1,a*2);
  79.         add(b*2-1,b*2);
  80.         add(a*2,b*2);
  81.         add(b*2,a*2);
  82.         }
  83.         else {
  84.         add(a*2,b*2-1);
  85.         add(b*2,a*2-1);
  86.         }
  87.     }
  88.     else if(op[1]=='O') {
  89.         if(c==1) {
  90.         add(a*2-1,b*2);
  91.         add(b*2-1,a*2);
  92.         }
  93.         else {//must choose 0
  94.         add(a*2,a*2-1);
  95.         add(b*2,b*2-1);
  96.         add(a*2-1,b*2-1);
  97.         add(b*2-1,a*2-1);
  98.         }
  99.     }
  100.     else {
  101.         if(c==1) {
  102.         add(a*2-1,b*2);
  103.         add(b*2-1,a*2);
  104.         add(b*2,a*2-1);
  105.         add(a*2,b*2-1);
  106.         }
  107.         else {
  108.         add(a*2,b*2);
  109.         add(b*2,a*2);
  110.         add(a*2-1,b*2-1);
  111.         add(b*2-1,a*2-1);   
  112.         }
  113.     }
  114.     }
  115.     siji(i,1,2*n) {
  116.     if(!dfn[i]) {
  117.         tarjan(i);
  118.     }
  119.     }
  120.     siji(i,1,n) {
  121.     if(col[i*2-1]==col[i*2] && col[i*2-1]!=0) {
  122.         puts("NO");
  123.         return;
  124.     }
  125.     }
  126.     puts("YES");
  127. }
  128. int main() {
  129. #ifdef ivorysi
  130.     freopen("f1.in","r",stdin);
  131. #endif
  132.     solve();
  134. }

POJ 2749 Building roads

Description

Farmer John's farm has N barns, and there are some cows that live in each barn. The cows like to drop around, so John wants to build some roads to connect these barns. If he builds roads for every pair of different barns, then he must build N * (N - 1) / 2 roads, which is so costly that cheapskate John will never do that, though that's the best choice for the cows.
Clever John just had another good idea. He first builds two transferring point S1 and S2, and then builds a road connecting S1 and S2 and N roads connecting each barn with S1 or S2, namely every barn will connect with S1 or S2, but not both. So that every pair of barns will be connected by the roads. To make the cows don't spend too much time while dropping around, John wants to minimize the maximum of distances between every pair of barns.
That's not the whole story because there is another troublesome problem. The cows of some barns hate each other, and John can't connect their barns to the same transferring point. The cows of some barns are friends with each other, and John must connect their barns to the same transferring point. What a headache! Now John turns to you for help. Your task is to find a feasible optimal road-building scheme to make the maximum of distances between every pair of barns as short as possible, which means that you must decide which transferring point each barn should connect to.
We have known the coordinates of S1, S2 and the N barns, the pairs of barns in which the cows hate each other, and the pairs of barns in which the cows are friends with each other.
Note that John always builds roads vertically and horizontally, so the length of road between two places is their Manhattan distance. For example, saying two points with coordinates (x1, y1) and (x2, y2), the Manhattan distance between them is |x1 - x2| + |y1 - y2|.

Input

The first line of input consists of 3 integers N, A and B (2 <= N <= 500, 0 <= A <= 1000, 0 <= B <= 1000), which are the number of barns, the number of pairs of barns in which the cows hate each other and the number of pairs of barns in which the cows are friends with each other.
Next line contains 4 integer sx1, sy1, sx2, sy2, which are the coordinates of two different transferring point S1 and S2 respectively.
Each of the following N line contains two integer x and y. They are coordinates of the barns from the first barn to the last one.
Each of the following A lines contains two different integers i and j(1 <= i < j <= N), which represent the i-th and j-th barns in which the cows hate each other.
The same pair of barns never appears more than once.
Each of the following B lines contains two different integers i and j(1 <= i < j <= N), which represent the i-th and j-th barns in which the cows are friends with each other. The same pair of barns never appears more than once.
You should note that all the coordinates are in the range [-1000000, 1000000].

Output

You just need output a line containing a single integer, which represents the maximum of the distances between every pair of barns, if John selects the optimal road-building scheme. Note if there is no feasible solution, just output -1.

Sample Input

4 1 1
12750 28546 15361 32055
6706 3887
10754 8166
12668 19380
15788 16059
3 4
2 3

Sample Output

53246

题解

2-SAT不能做带限制的东西
然而这个东西……要求最大值最小
这让我们想到二分答案！
2-SAT当然是只能判可行解啦！！！
然后我们判断两个点链接方式的不同会不会大于我们二分到的答案，然后根据这新得的限制关系判断是否可行

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MAXN 10005
  12. #define mod 1000000007
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. ll read() {
  17.     ll res=0,neg=1;
  18.     char c=getchar();
  19.     while(c<'0' || c>'9') {
  20.     if(c=='-') neg=-1;
  21.     c=getchar();
  22.     }
  23.     while(c>='0' && c<='9') {
  24.     res=res*10+c-'0';
  25.     c=getchar();
  26.     }
  27.     return res*neg;
  28. }
  29. struct node {
  30.     int to,next;
  31. }edge[4000005];
  32. int head[MAXN*2],sumedge;
  33. int dfn[MAXN*2],low[MAXN*2],inx,instack[MAXN*2],col[MAXN*2],tot;
  34. stack<int> st;
  35. void add(int u,int v) {
  36.     edge[++sumedge].to=v;
  37.     edge[sumedge].next=head[u];
  38.     head[u]=sumedge;
  39. }
  40. void addtwo(int u,int v) {
  41.     add(u,v);add(v,u);
  42. }
  43. void tarjan(int u) {
  44.     dfn[u]=low[u]=++inx;
  45.     st.push(u);
  46.     instack[u]=1;
  47.     for(int i=head[u];i;i=edge[i].next) {
  48.     int v=edge[i].to;
  49.     if(!dfn[v]) {
  50.         tarjan(v);
  51.         low[u]=min(low[u],low[v]);
  52.     }
  53.     else if(instack[v]==1) {
  54.         low[u]=min(dfn[v],low[u]);
  55.     }
  56.     }
  57.     if(low[u]==dfn[u]) {
  58.     ++tot;
  59.     int x;
  60.     while(1) {
  61.         x=st.top();st.pop();
  62.         col[x]=tot;
  63.         instack[x]=2;
  64.         if(x==u) break;
  65.     }
  66.     }
  67. }
  68. int dis;
  69. int x[MAXN],y[MAXN],n,A,B,c[MAXN],d[MAXN];
  70. int dist(int l,int z) {
  71.     return abs(x[l]-x[z])+abs(y[l]-y[z]);
  72. }
  73. bool check(int limit) {
  74.     sumedge=0;
  75.     tot=0;
  76.     inx=0;
  77.     memset(head,0,sizeof(head));
  78.     memset(dfn,0,sizeof(dfn));
  79.     memset(low,0,sizeof(low));
  80.     memset(col,0,sizeof(col));
  81.     memset(instack,0,sizeof(instack));
  82.     siji(i,1,A) {
  83.     add(c[i],d[i]+n);
  84.     add(d[i],c[i]+n);
  85.     add(c[i]+n,d[i]);
  86.     add(d[i]+n,c[i]);
  87.     }
  88.     siji(i,A+1,A+B) {
  89.     add(c[i],d[i]);
  90.     add(d[i],c[i]);
  91.     add(c[i]+n,d[i]+n);
  92.     add(d[i]+n,c[i]+n);
  93.     }
  94.     siji(i,1,n) {
  95.     siji(j,i+1,n) {
  96.         if(dist(i,n+1)+dist(j,n+1) > limit) {
  97.         add(i,j+n);
  98.         add(j,i+n);
  99.         }
  100.         if(dist(i,n+2)+dist(j,n+2) > limit) {
  101.         add(i+n,j);
  102.         add(j+n,i);
  103.         }
  104.         if(dist(i,n+1)+dist(j,n+2)+dis > limit) {
  105.         add(i,j);
  106.         add(j+n,i+n);
  107.         }
  108.         if(dist(i,n+2)+dist(j,n+1)+dis > limit) {
  109.         add(i+n,j+n);
  110.         add(j,i);
  111.         }
  112.     }
  113.     }
  114.     siji(i,1,2*n) {
  115.     if(!dfn[i]) {
  116.         tarjan(i);
  117.     }
  118.     }
  119.     siji(i,1,n) {
  120.     if(col[i]==col[i+n]) return false;
  121.     }
  122.     return true;
  123. }
  124. void solve() {
  125.     n=read();
  126.     A=read();
  127.     B=read();
  128.     x[n+1]=read();y[n+1]=read();x[n+2]=read();y[n+2]=read();
  129.     dis=abs(x[n+1]-x[n+2])+abs(y[n+1]-y[n+2]);
  131.     siji(i,1,n) {
  132.     x[i]=read();y[i]=read();
  133.     }
  134.     siji(i,1,A+B) {
  135.     c[i]=read();d[i]=read();
  136.     }
  137.     int l=0,r=10000000;
  139.     while(l<r) {
  140.     int mid=(l+r)>>1;
  141.     if(check(mid)) {
  142.         r=mid;
  143.     }
  144.     else {
  145.         l=mid+1;
  146.     }
  147.     }
  148.     if(l==10000000) {
  149.     puts("-1");
  150.     return;
  151.     }
  152.     printf("%d\n",r);
  153. }
  154. int main() {
  155. #ifdef ivorysi
  156.     freopen("f1.in","r",stdin);
  157. #endif
  158.     solve();
  160. }

欧拉回路

http://www.cnblogs.com/ivorysi/p/5745005.html

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注