[DLX精确覆盖] hdu 3663 Power Stations

题意：

给你n、m、d，，代表有n个城市，m条城市之间的关系，每个城市要在日后d天内都有电。

对于每个城市，都有一个发电站，每个发电站可以在[a,b]的每一个连续子区间内发电。

x城市发电了，他相邻的城市也有电，并且每个发电站只能启动一次，或者不启动。

现在问，如何安排发电站的启动，保证每个城市d天都有电。

输出发电方案，不发电的话输出0 0

思路：

一个简单的精确覆盖问题，就是建图比较麻烦一点。

这里考虑到每天都要得到电，所以把每个城市每天都设为列（n*d）

然后每个城市对于[a,b]的所有子区间，作为行。

然后对于每个城市只能启动1次，所以需要添加n行，代表每个城市发过点没。

所以列是n*d+n。

还需要注意的是，在判断dance成立的时候，只要判断R[0]==0 || R[0]>n*d

因为每个发电站不一定要发电。

代码：

#include"stdio.h"#include"algorithm"#include"string.h"#include"iostream"#include"queue"#include"map"#include"vector"#include"string"using namespace std;#define N 2010*(66*6)#define M 2010int ooo;struct DLX{int n,m,C;int U[N],D[N],L[N],R[N],Row[N],Col[N];int H[M],S[M],cnt,ans[M];void init(int _n,int _m){n=_n;m=_m;for(int i=0; i<=m; i++){U[i]=D[i]=i;L[i]=(i==0?m:i-1);R[i]=(i==m?0:i+1);S[i]=0;}C=m;for(int i=1; i<=n; i++) H[i]=-1;}void link(int x,int y){C++;Row[C]=x;Col[C]=y;S[y]++;U[C]=U[y];D[C]=y;D[U[y]]=C;U[y]=C;if(H[x]==-1) H[x]=L[C]=R[C]=C;else{L[C]=L[H[x]];R[C]=H[x];R[L[H[x]]]=C;L[H[x]]=C;}}void del(int x){R[L[x]]=R[x];L[R[x]]=L[x];for(int i=D[x]; i!=x; i=D[i]){for(int j=R[i]; j!=i; j=R[j]){U[D[j]]=U[j];D[U[j]]=D[j];S[Col[j]]–;}}}void rec(int x){for(int i=U[x]; i!=x; i=U[i]){for(int j=L[i]; j!=i; j=L[j]){U[D[j]]=j;D[U[j]]=j;S[Col[j]]++;}}R[L[x]]=x;L[R[x]]=x;}int dance(int x){if(R[0]==0 || R[0]>ooo) //判定条件{cnt=x;return 1;}int now=R[0];for(int i=R[0]; i!=0 && i<=ooo; i=R[i]) //这里注意也要改{if(S[i]<S[now]) now=i;}del(now);for(int i=D[now]; i!=now; i=D[i]){ans[x]=Row[i];for(int j=R[i]; j!=i; j=R[j]) del(Col[j]);if(dance(x+1)) return 1;for(int j=L[i]; j!=i; j=L[j]) rec(Col[j]);}rec(now);return 0;}} dlx;struct node{int a,b;} kx[66];struct answer{int id,x,y;}daan[2002];int main(){int n,m,d;while(scanf("%d%d%d",&n,&m,&d)!=-1){ooo=n*d;int v[66][66];memset(v,0,sizeof(v));while(m–){int a,b;scanf("%d%d",&a,&b);v[a][b]=v[b][a]=1;}int cnt=0;for(int i=1; i<=n; i++){scanf("%d%d",&kx[i].a,&kx[i].b);for(int j=kx[i].a; j<=kx[i].b; j++) for(int k=j; k<=kx[i].b; k++) cnt++;}dlx.init(cnt,n*d+n);cnt=0;for(int i=1; i<=n; i++){for(int j=kx[i].a; j<=kx[i].b; j++){for(int k=j; k<=kx[i].b; k++){++cnt;daan[cnt].id=i;daan[cnt].x=j;daan[cnt].y=k;for(int l=j; l<=k; l++){dlx.link(cnt,(i-1)*d+l);for(int u=1;u<=n;u++){if(v[i][u]){//printf("%d %d %d\n",i,u,l);dlx.link(cnt,(u-1)*d+l);}}}dlx.link(cnt,n*d+i);}}}int ans=dlx.dance(0);if(ans==0) puts("No solution");else{int us[66];memset(us,0,sizeof(us));for(int i=0;i<dlx.cnt;i++) us[daan[dlx.ans[i]].id]=dlx.ans[i];for(int i=1;i<=n;i++){if(us[i]==0) printf("0 0\n");else printf("%d %d\n",daan[us[i]].x,daan[us[i]].y);}}puts("");}return 0;}

版权声明：本文为博主原创文章，未经博主允许不得转载。

也不要说曾经失去，失去的不是永远失去，得到的不是永远拥有，