hdu 3663 Power Stations[DLX]
题意：给你一个最多60个点150个边的无向图，每个点是一个村庄，每个村庄都有一个发电站，每个电站可以给它所在的村庄和它有边直接连接的所有村庄供电，现在让你选出一些电站，使每个村庄都能被供电且每个村庄只被一个电站供电。另外，每个村庄的发电站都只能在1-d天内的一个子区间工作，你需要安排它在哪几天来工作，且每个电站一旦工作结束就不能再次启动，即它工作的时间是连续的。d小于等于5。方案可能有多组，输出任意一组即可，无解输出No solution
分析：首先每个点必须被覆盖且只被覆盖一次，很容易想到精确覆盖，再者边数为150远小于完全图，即是个稀疏图，所以转化成矩阵之后也是稀疏的，所以DLX优势很明显。再看一下数据规模，基本就可以确定很大可能是DLX了，感觉这题还是很裸的。
我得想法：
1.首先每个点的每一天要对应一个列，即每个点的每一天都要被盖且只被盖一次；
2.对于每个电站的工作区间必须连续这一要求，可以给每一个电站（即每一个点）再加上一列，选用就标1，只要是同一个电站就只能被取一次；
3.基于第二点，如果一个点没有被选作电站，那么它电站的对应列就没有被选，为了当这种情况发生时不至于无解，可以对应每一个点都再多加一行，使该行只有选为电站的位置为1，其他位置为0，这样就可以了，否则2的构造方法就是错的。
共n*d+n列，前n*d表示每个点对应在第i天是否被供电，后n列表示每个点是否被选择，注意上面的第三点。还有就是要输出空行!
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1111111;
const int inf=0x3f3f3f3f;
#define ff(i,a,s) for(int i=a[s];i!=s;i=a[i])
struct DLX
{
int row,col,cnt,tot,ans[N];
int u[N],d[N],l[N],r[N],s[N];
int head,rr[N],cc[N];
void del(int &c)
{
l[r[c]]=l[c],r[l[c]]=r[c];
ff(i,d,c) ff(j,r,i) u[d[j]]=u[j],d[u[j]]=d[j],--s[cc[j]];
}
void cancel(int &c)
{
ff(i,u,c) ff(j,l,i) ++s[cc[j]],u[d[j]]=j,d[u[j]]=j;
l[r[c]]=c,r[l[c]]=c;
}
int node(int up,int down,int left,int right)
{
u[cnt]=up,d[cnt]=down,l[cnt]=left,r[cnt]=right;
d[up]=u[down]=r[left]=l[right]=cnt;
return cnt++;
}
void init(int c)
{
tot=0,col=c,cnt=0;
for(int i=0;i<c;i++)
{
if(i) cc[i]=node(cnt,cnt,l[0],0);
else cc[i]=node(0,0,0,0);
s[i]=0;
}
head=node(cnt,cnt,l[0],0);
}
void insert(int *a,int n,int now)
{
int p,f;
for(int i=0;i<n;i++)
{
if(i) p=node(u[a[i]],a[i],l[f],f);
else p=f=node(u[a[i]],a[i],cnt,cnt);
rr[p]=now,cc[p]=a[i],s[a[i]]++;
}
}
int search()
{
if(r[head]==head) return 1;
int ch,tmp=inf;
ff(i,r,head) if(s[i]<tmp) ch=i,tmp=s[i];
del(ch);
ff(i,d,ch)
{
ans[tot++]=rr[i];
ff(j,r,i) del(cc[j]);
if(search()) return true;
tot--;
ff(j,l,i) cancel(cc[j]);
}
cancel(ch);
return false;
}
int output(int *a)
{
for(int i=0;i<tot;i++) a[i]=ans[i];
return tot;
}
}dlx;
int ev[333],nxt[333],head[66],e;
int arr[3333],idx,id[3333],l[3333],r[3333];
int n,m,d,x,y;
void add(int u,int v)
{
ev[e]=v,nxt[e]=head[u],head[u]=e++;
ev[e]=u,nxt[e]=head[v],head[v]=e++;
}
void deal(int u,int st,int ed)//u点在[st,ed]区间被选，对应的01状态
{
int cnt=0;arr[cnt++]=n*d+u;
for(int i=st;i<=ed;i++) arr[cnt++]=u*d+i;
for(int i=head[u];~i;i=nxt[i]) for(int j=st;j<=ed;j++) arr[cnt++]=ev[i]*d+j;
sort(arr,arr+cnt); cnt=unique(arr,arr+cnt)-arr;//去重
id[idx]=u,l[idx]=st,r[idx]=ed;//记录这一行对应id,l,r
dlx.insert(arr,cnt,idx++);
}
int ansl[3333],ansr[3333];
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d%d",&n,&m,&d)!=EOF)
{
memset(head,-1,sizeof(head));e=idx=0;
for(int i=0;i<m;i++) scanf("%d%d",&x,&y),add(x-1,y-1);
dlx.init(n*d+n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&x,&y);x--,y--;
for(int st=x;st<=y;st++) for(int ed=st;ed<=y;ed++) deal(i,st,ed);
arr[0]=n*d+i;id[idx]=i,l[idx]=r[idx]=-1;//u点不被选时，对应的01状态
dlx.insert(arr,1,idx++);
}
if(dlx.search())
{
int cnt=dlx.output(arr);
for(int i=0;i<cnt;i++) ansl[id[arr[i]]]=l[arr[i]],ansr[id[arr[i]]]=r[arr[i]];
for(int i=0;i<n;i++) printf("%d %d/n",ansl[i]+1,ansr[i]+1);
}
else puts("No solution");
puts("");
}
return 0;
}
