思路:把每个点拆成(d+1)*n列,行数为可拆分区间数。对所有的有i号点拆分出来的行都要建一条该行到i列的边,那么就能确保有i号点拆出来的行只能选择一行。
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define Maxn 1010
#define Maxm 80002
#define LL __int64
#define Abs(x) ((x)>0?(x):(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define inf 100000
#define lowbit(x) (x&(-x))
#define clr(x,y) memset(x,y,sizeof(x))
#define Mod 1000000007
using namespace std;
int U[Maxn*],D[Maxn*],L[Maxn*],R[Maxn*],S[Maxn*],H[Maxn],C[Maxn*],road[Maxn],id,d,n,m;
int g[][],row[Maxn*];
int vi[Maxn];
struct interv{
int s,e,i;
int operator <(const interv &temp) const{
if(s==temp.s)
return e>temp.e;
return s<temp.s;
}
}p[Maxn],ans[Maxn];
void init(int n)
{
int i;
for(i=;i<=n;i++){
D[i]=U[i]=i;
L[i+]=i;
R[i]=i+;
S[i]=;
}
R[n]=;
id=n+;
memset(H,-,sizeof(H));
}
void ins(int r,int c)
{
int i,j;
D[id]=D[c];
U[id]=c;
U[D[c]]=id;
D[c]=id;
if(H[r]<)
H[r]=L[id]=R[id]=id;
else{
L[id]=H[r];
R[id]=R[H[r]];
L[R[H[r]]]=id;
R[H[r]]=id;
}
S[c]++;
row[id]=r;
C[id++]=c;
}
void Remove(int c)
{
int i,j;
L[R[c]]=L[c];
R[L[c]]=R[c];
for(i=D[c];i!=c;i=D[i]){
for(j=R[i];j!=i;j=R[j]){
D[U[j]]=D[j];
U[D[j]]=U[j];
S[C[j]]--;
}
}
}
void Resume(int c)
{
int i,j;
L[R[c]]=c;
R[L[c]]=c;
for(i=D[c];i!=c;i=D[i]){
for(j=R[i];j!=i;j=R[j]){
D[U[j]]=j;
U[D[j]]=j;
S[C[j]]++;
}
}
}
bool dfs(int step)
{
int i,j,k,c,temp;
if(R[]==){
for(i=;i<step;i++)
vi[ans[road[i]].i]=road[i];
for(i=;i<=n;i++){
if(!vi[i]) printf("0 0\n");
else printf("%d %d\n",ans[vi[i]].s,ans[vi[i]].e);
}
return true;
}
temp=inf;
for(i=R[];i;i=R[i]) if(S[i]<temp){
temp=S[i];
c=i;
}
Remove(c);
for(i=D[c];i!=c;i=D[i]){
road[step]=row[i];
for(j=R[i];j!=i;j=R[j]){
Remove(C[j]);
}
if(dfs(step+))
return true;
for(j=L[i];j!=i;j=L[j])
Resume(C[j]);
}
Resume(c);
return false;
}
void build()
{
int i,j,sz,k,r;
init(n*(d+));
int cnt=;
for(i=;i<=n;i++){
for(j=p[i].s;j<=p[i].e;j++){
for(k=p[i].s;k<=j;k++){
ins(cnt,i);
ans[cnt].s=k,ans[cnt].e=j,ans[cnt].i=i;
for(r=;r<=n;r++){
if(!g[i][r]) continue;
for(int d=k;d<=j;d++){
ins(cnt,n+(d-)*n+r);
}
}
cnt++;
}
}
ins(cnt,i);
ans[cnt].s=,ans[cnt].e=,ans[cnt].i=i;
cnt++;
}
}
int main()
{
int i,j,u,v;
while(scanf("%d%d%d",&n,&m,&d)!=EOF){
memset(g,,sizeof(g));
for(i=;i<=m;i++){
scanf("%d%d",&u,&v);
g[u][v]=g[v][u]=;
}
for(i=;i<=n;i++){
g[i][i]=;
scanf("%d%d",&p[i].s,&p[i].e);
p[i].i=i;
}
build();
if(!dfs())
printf("No solution\n");
printf("\n");
}
return ;
}