題意：給你一個最多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;
}
