好久不写博客,这段时间实在是有点忙…写的题都没空发上来,马上就是区域赛了,现在一直在攻图论(毕竟软肋),希望能在区域赛有所帮助。
HDU 3062 Party
题目链接
题目大意
现有n对夫妻和一个聚会,聚会要求n个人参加,每对夫妻需要出一个人参加聚会,但是某些人之间又有矛盾,现在给出矛盾关系,让你求是否可能举办Party 。
题解
2-SAT模板题,相当于有n个点,某两个点的状态之间是矛盾的。于是我们可以据此建边,然后跑一遍\(tarjan\)就可以了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define maxn 1005
using namespace std;
int n,m,a1,a2,c1,c2,pre[maxn*2],cnt,dfn[maxn*2],low[maxn*2],p;
int sta[maxn*2],h,Cnt,scc[maxn*2];
struct edge
{
int u,v,next;
};
edge e[maxn*maxn*2];
bool vis[maxn*2];
vector<int> v[maxn*2];
void addedge(int u,int v)
{
e[cnt].u=u; e[cnt].v=v; e[cnt].next=pre[u];
pre[u]=cnt++;
}
void tarjan(int u)
{
low[u]=dfn[u]=p++;
vis[u]=1;
sta[h++]=u;
for (int i=pre[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (vis[v]) low[u]=min(low[u],dfn[v]);
}
if (low[u]==dfn[u])
{
int c=2*n;
while (c!=u)
{
c=sta[--h]; scc[c]=Cnt;
vis[c]=0; sta[h]=0;
v[Cnt].push_back(c);
}
Cnt++;
}
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(pre,-1,sizeof(pre));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low)); cnt=0;
memset(vis,0,sizeof(vis));
memset(scc,0,sizeof(scc)); Cnt=0;
h=0;
for (int i=0;i<m;i++)
{
scanf("%d%d%d%d",&a1,&a2,&c1,&c2);
addedge(a1*2+c1,(a2*2+c2)^1 );
addedge(a2*2+c2,(a1*2+c1)^1 );
}
p=1;
for (int i=0;i<2*n;i++) v[i].clear();
for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
bool f=0;
for (int i=0;i<n*2;i+=2) if (scc[i]==scc[i+1])
{
f=1; break;
}
if (f) printf("NO\n");
else printf("YES\n");
}
return 0;
}
POJ 3648 Wedding
题目链接
题目大意&题解
这一题题目意思比较奇怪…看了别人的博客才看懂题目是什么意思…大概就是说有2n个人要坐在新娘的对面,但是这些人里面不能有夫妻,也不能有搞基的…我们按照题目给的关系建图就可以了,只不过这一题要输出解。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define maxn 1005
using namespace std;
char a,b;
int n,m,x1,x2,p,cnt,pre[maxn<<1],dfn[maxn*2],low[maxn*2];
int sta[maxn*2],h,de[maxn*2],num,scc[maxn*2],opp[maxn*2],col[maxn<<1];
struct edge
{
int u,v,next;
};
edge e[maxn*maxn*2];
bool vis[maxn*2];
vector<int> G[maxn*2];
void addedge(int u,int v)
{
e[cnt].u=u; e[cnt].v=v; e[cnt].next=pre[u];
pre[u]=cnt++;
}
void tarjan(int u)
{
dfn[u]=low[u]=p++;
vis[u]=1; sta[h++]=u;
for (int i=pre[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (vis[v]) low[u]=min(low[u],dfn[v]);
}
if (low[u]==dfn[u])
{
int v;
do
{
v=sta[--h];
vis[v]=0;
scc[v]=num;
}
while (v!=u);
num++;
}
}
bool Check()
{
for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
for (int i=0;i<2*n;i+=2) if (scc[i]==scc[i+1]) return 0;
for (int i=0;i<2*n;i+=2) opp[scc[i]]=scc[i+1],opp[scc[i+1]]=scc[i];
return 1;
}
void buildmap()
{
for (int i=0;i<num;i++) G[i].clear();
for (int i=0;i<cnt;i++)
{
int u,v;
u=e[i].u; v=e[i].v;
if (scc[u]!=scc[v])
{
G[scc[v]].push_back(scc[u]);
de[scc[u]]++;
}
}
}
void solve()
{
queue<int> q;
memset(col,0,sizeof(col));
for (int i=0;i<num;i++) if (!de[i]) q.push(i);
while (!q.empty())
{
int v=q.front(); q.pop();
if (!col[v])
{ col[v]=1; col[opp[v]]=2; }
for (int i=0;i<G[v].size();i++)
{
de[G[v][i]]--;
if (de[G[v][i]]==0) q.push(G[v][i]);
}
}
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(pre,-1,sizeof(pre));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
cnt=0; p=1;
for (int i=0;i<m;i++)
{
scanf("%d%c %d%c",&x1,&a,&x2,&b);
if (a=='h' && b=='h') addedge(x1*2+1,x2*2),addedge(x2*2+1,x1*2);
else if (a=='h' && b=='w') addedge(x1*2+1,x2*2+1),addedge(x2*2,x1*2);
else if (a=='w' && b=='h') addedge(x1*2,x2*2),addedge(x2*2+1,x1*2+1);
else addedge(x1*2,x2*2+1),addedge(x2*2,x1*2+1);
}
addedge(0,1);
if (Check())
{
buildmap();
solve();
for (int i=2;i<2*n;i++) if (col[scc[i]]==1)
{
if (i&1) printf("%dw ",i/2);
else printf("%dh ",i/2);
}
}
else printf("bad luck\n");
}
return 0;
}
POJ 3207 Ikki’s Story IV - Panda’s Trick
题目链接
题目大意&题解
这个题比较有意思一点。说是n个点,标号从0到n,现在有若干条线段,可以从园内连也可以从圆外连,每条线段的端点都是这n个点中的某两个,现在告诉你一个点不会成为两个线段的端点,问你这若干条线段是否会相交。
可以先将线段按照右端点排序,然后判断两条线段之间是否会冲突(冲突的意思就是比如一条线段从圆内连,另外一条线段就必须要从圆外面连),我们根据冲突建边之后,跑一遍\(tarjan\)就可以了。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 1005
#define maxm 505
using namespace std;
int n,m,pre[maxn<<1],cnt,dfn[maxn<<1],low[maxn<<1],p;
int sta[maxn<<1],h,scc[maxn<<1],num;
bool vis[maxn*2];
struct line
{
int l,r;
bool operator <(const line &x) const
{
if (r!=x.r)return r<x.r;
return l<x.l;
}
};
line L[maxm];
struct edge
{
int u,v,next;
};
edge e[maxm*maxm];
void addedge(int u,int v)
{
e[cnt].u=u; e[cnt].v=v;
e[cnt].next=pre[u]; pre[u]=cnt++;
}
void tarjan(int u)
{
dfn[u]=low[u]=p++;
vis[u]=1;
sta[h++]=u;
for (int i=pre[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (vis[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u])
{
int c;
do
{
c=sta[--h];
vis[c]=0;
scc[c]=num;
}
while (c!=u) ;
num++;
}
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(pre,-1,sizeof(pre));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(sta,0,sizeof(sta)); h=0;
memset(scc,0,sizeof(scc));
memset(vis,0,sizeof(vis));
int l,r; p=1; cnt=0;
for (int i=0;i<m;i++) scanf("%d%d",&L[i].l,&L[i].r);
sort(L,L+m);
for (int i=m-1;i>=0;i--)
for (int j=i-1;j>=0;j--)
if (L[j].r>L[i].l && L[j].l<L[i].l)
{
addedge(L[j].l*2,L[i].l*2+1); addedge(L[j].l*2+1,L[i].l*2);
addedge(L[i].l*2+1,L[j].l*2); addedge(L[i].l*2,L[j].l*2+1);
}
bool f=0;
for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
for (int i=0;i<2*n;i+=2) if (scc[i]==scc[i+1])
{
f=1;
break;
}
if (f) printf("the evil panda is lying again\n");
else printf("panda is telling the truth...\n");
}
return 0;
}
POJ 3678 Katu Puzzle
题目链接
题目大意&题解
最裸的2-SAT了,n个值,告诉你每两个值之间的关系\((or,and,xor == 0/1)\),现在让你求是否合法。
直接建立矛盾关系在图上跑一遍就行啦~
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 1000
#define maxm 1000005
using namespace std;
int n,m,cnt,pre[maxn<<1],dfn[maxn<<1],low[maxn<<1];
int scc[maxn<<1],p,sta[maxn<<1],h,num;
struct edge
{
int u,v,next;
};
edge e[maxm];
bool vis[maxn<<1];
void addedge(int u,int v)
{
e[cnt].u=u; e[cnt].v=v;
e[cnt].next=pre[u]; pre[u]=cnt++;
}
void tarjan(int u)
{
dfn[u]=low[u]=p++;
vis[u]=1; sta[h++]=u;
for (int i=pre[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (vis[v]) low[u]=min(dfn[v],low[u]);
}
if (dfn[u]==low[u])
{
int c;
do
{
c=sta[--h];
vis[c]=0;
scc[c]=num;
}
while (c!=u);
num++;
}
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(pre,-1,sizeof(pre)); cnt=0;
memset(dfn,0,sizeof(dfn)); p=1;
memset(low,0,sizeof(low)); h=0;
memset(scc,0,sizeof(scc)); num=0;
int a,b,c; char s[5];
for (int i=0;i<m;i++)
{
scanf("%d%d%d%s",&a,&b,&c,s);
if (s[0]=='A')
{
if (c) addedge(a*2+1,a*2),addedge(b*2+1,b*2);
else addedge(a*2,b*2+1),addedge(b*2,a*2+1);
}
else if (s[0]=='O')
{
if (c) addedge(a*2+1,b*2),addedge(b*2+1,a*2);
else addedge(a*2,a*2+1),addedge(b*2,b*2+1);
}
else if (s[0]=='X')
{
if (c)
{
addedge(a*2,b*2+1); addedge(b*2,a*2+1);
addedge(b*2+1,a*2); addedge(a*2+1,b*2);
}
else
{
addedge(a*2,b*2); addedge(a*2+1,b*2+1);
addedge(b*2,a*2); addedge(b*2+1,a*2+1);
}
}
}
bool f=0;
for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
for (int i=0;i<2*n;i+=2) if (scc[i]==scc[i+1])
{
f=1;
break ;
}
if (f) printf("NO\n");
else printf("YES\n");
}
return 0;
}
HDU 4421 Bit Magic
题目链接
题目大意&题解
这一题就是上一题的升级版,他现在把1位关系变成了32位关系,让你求是否可行。
一样的做法,对每一位建图跑一遍就行了。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 505
using namespace std;
int n,b[maxn][maxn],pre[maxn<<1],scc[maxn<<1],dfn[maxn<<1],low[maxn<<1];
int cnt,sta[maxn<<1],h,p,num;
bool vis[maxn<<1];
struct edge
{
int u,v,next;
};
edge e[maxn*maxn*4];
void addedge(int u,int v)
{
e[cnt].u=u; e[cnt].v=v;
e[cnt].next=pre[u]; pre[u]=cnt++;
}
void tarjan(int u)
{
dfn[u]=low[u]=p++;
vis[u]=1; sta[h++]=u;
for (int i=pre[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (vis[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u])
{
int v;
do
{
v=sta[--h];
vis[v]=0;
scc[v]=num;
}
while (v!=u) ;
num++;
}
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
for (int i=0;i<n;i++)
for (int j=0;j<n;j++) scanf("%d",&b[i][j]);
bool f=0;
for (int k=0;k<32;k++)
{
memset(pre,-1,sizeof(pre)); cnt=0;
memset(dfn,0,sizeof(dfn)); num=0;
memset(low,0,sizeof(low)); p=1;
memset(scc,0,sizeof(scc)); h=0;
for (int i=0;i<n;i++)
for (int j=0;j<i;j++)
{
if ((i&1) && (j&1) ) // |
{
if ((1<<k)&b[i][j]) addedge(i*2+1,j*2),addedge(j*2+1,i*2);
else addedge(i*2,i*2+1),addedge(j*2,j*2+1);
}
else if (!(i&1) && !(j&1) ) // &
{
if ((1<<k)&b[i][j]) addedge(i*2+1,i*2),addedge(j*2+1,j*2);
else addedge(i*2,j*2+1),addedge(j*2,i*2+1);
}
else if ((1<<k)&b[i][j])
{
addedge(i*2,j*2+1); addedge(j*2+1,i*2);
addedge(j*2,i*2+1); addedge(i*2+1,j*2);
}
else
{
addedge(i*2,j*2); addedge(j*2,i*2);
addedge(i*2+1,j*2+1); addedge(j*2+1,i*2+1);
}
}
for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
for (int i=0;i<2*n;i+=2) if (scc[i]==scc[i+1])
{
f=1; break;
}
if (f) break;
}
if (f) printf("NO\n");
else printf("YES\n");
}
return 0;
}