最近研究可行性null，稍微总结一下，以后继续补充：
二分+2sat判可行性
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1024*2+9;
int doorx[1<<12],doory[1<<12],x[maxn],y[maxn];
int n,m;
int dfn[maxn<<1],low[maxn<<1],stack[maxn<<1],instack[maxn<<1],s[maxn<<1];
int count,top,con;
int head[maxn<<1],lon;
struct
{
int next,to;
}e[1000000];
void edgemake(int from,int to)
{
e[++lon].to=to;
e[lon].next=head[from];
head[from]=lon;
}
void edgeini()
{
memset(head,-1,sizeof(head));
lon=-1;
}
void tarjan(int t)
{
dfn[t]=low[t]=++count;
stack[++top]=t;
instack[t]=1;
for(int k=head[t];k!=-1;k=e[k].next)
{
int u=e[k].to;
if(dfn[u]==-1)
{
tarjan(u);
low[t]=min(low[t],low[u]);
}
else if(instack[u]==1)
low[t]=min(low[t],dfn[u]);
}
if(dfn[t]==low[t])
{
++con;
while(1)
{
int u=stack[top--];
instack[u]=0;
s[u]=con;
if(u==t) break;
}
}
}
void tarjan()
{
memset(dfn,-1,sizeof(dfn));
memset(instack,0,sizeof(instack));
count=top=con=0;
for(int i=0;i<=n*2*2-1;i++)
if(dfn[i]==-1)
tarjan(i);
}
bool check()
{
for(int i=0;i<=n*4-1-1;i+=2)
if(s[i]==s[i+1])
return false;
return true;
}
bool check(int ret)
{
edgeini();
for(int i=1;i<=n;i++)
{
edgemake(x[i]*2,y[i]*2+1);
edgemake(y[i]*2,x[i]*2+1);
}
for(int i=1;i<=ret;i++)
{
edgemake(2*doorx[i]+1,2*doory[i]);
edgemake(2*doory[i]+1,2*doorx[i]);
}
tarjan();
return check();
}
int main()
{
while(scanf("%d %d",&n,&m),n||m)
{
edgeini();
for(int i=1,tmp;i<=n;i++)
{
scanf("%d %d",&x[i],&y[i]);
}
for(int i=1;i<=m;i++)
scanf("%d %d",&doorx[i],&doory[i]);
int st=0,ed=m;
while(st<ed)
{
int mid=(st+ed+1)>>1;
if(check(mid))
st=mid;
else
ed=mid-1;
}
printf("%d\n",st);
}
return 0;
}
文章结束给大家分享下程序员的一些笑话语录： 神灯新篇
一个程序员在海滩上发现了一盏神灯。他在灯上擦了几下，一个妖怪就从灯里跳出来说：“我是世界上法术最强的妖怪。我可以实现你的任何梦想，但现在，我只能满足你一个愿望。”程序员摊开了一幅中东地图说：“我想让中东得到永久的和平。”妖怪答道：“哦，我没办法。自打创世纪以来，那里的战火就没有停息过。这世上几乎没有我办不到的事，但这件事除外。”程序员于是说：“好吧，我是一个程序员，为许多用户编写过程序。你能让他们把需求表述得更清楚些，并且让我们的软件项目有那么一两次按进度按成本完成吗？”妖怪说：“唔，我们还是来看中东地图吧。”