【题目链接】
http://acm.hdu.edu.cn/showproblem.php?pid=3663
【算法】
先建图，然后用Dancing Links求解精确覆盖，即可
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500000 int i,j,k,l,m,cnt,N,M,D,u,v;
bool g[][];
struct Time
{
int s,e;
} ans[],a[];
struct info
{
int l,r,pos;
} R[MAXN]; struct DancingLinks
{
int n,m,step,size;
int U[MAXN],D[MAXN],L[MAXN],R[MAXN],Row[MAXN],Col[MAXN];
int H[MAXN],S[MAXN];
int ans[MAXN];
inline void init(int _n,int _m)
{
int i;
n = _n;
m = _m;
for (i = ; i <= m; i++)
{
S[i] = ;
U[i] = D[i] = i;
L[i] = i - ;
R[i] = i + ;
}
L[] = m; R[m] = ;
size = m;
for (i = ; i <= n; i++) H[i] = -;
}
inline void link(int r,int c)
{
size++;
Row[size] = r;
Col[size] = c;
S[c]++;
D[size] = D[c];
U[D[c]] = size;
U[size] = c;
D[c] = size;
if (H[r] < ) L[size] = R[size] = H[r] = size;
else
{
R[size] = R[H[r]];
L[R[H[r]]] = size;
L[size] = H[r];
R[H[r]] = size;
}
}
inline void Remove(int c)
{
int i,j;
R[L[c]] = R[c];
L[R[c]] = L[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[Col[j]]--;
}
}
}
inline void Resume(int c)
{
int i,j;
for (i = U[c]; i != c; i = U[i])
{
for (j = L[i]; j != i; j = L[j])
{
D[U[j]] = j;
U[D[j]] = j;
S[Col[j]]++;
}
}
L[R[c]] = c;
R[L[c]] = c;
}
inline bool solve(int dep)
{
int i,j,c;
if (R[] == )
{
step = dep;
return true;
}
c = R[];
for (i = R[]; i != ; i = R[i])
{
if (S[i] < S[c])
c = i;
}
Remove(c);
for (i = D[c]; i != c; i = D[i])
{
ans[dep] = Row[i];
for (j = R[i]; j != i; j = R[j])
Remove(Col[j]);
if (solve(dep+)) return true;
for (j = L[i]; j != i; j = L[j])
Resume(Col[j]);
}
Resume(c);
return false;
}
} DLX; int main()
{ while (scanf("%d%d%d",&N,&M,&D) != EOF)
{
cnt = ;
memset(g,false,sizeof(g));
DLX.init(N*,N*D+N);
for (i = ; i <= M; i++)
{
scanf("%d%d",&u,&v);
g[u][v] = g[v][u] = true;
}
for (i = ; i <= N; i++) g[i][i] = true;
for (i = ; i <= N; i++) scanf("%d%d",&a[i].s,&a[i].e);
for (i = ; i <= N; i++)
{
for (j = a[i].s; j <= a[i].e; j++)
{
for (k = j; k <= a[i].e; k++)
{
DLX.link(cnt,i);
R[cnt] = (info){j,k,i};
for (l = ; l <= N; l++)
{
if (g[i][l])
{
for (m = j; m <= k; m++)
{
DLX.link(cnt,N+(l-)*D+m);
}
}
}
cnt++;
}
}
DLX.link(cnt,i);
R[cnt] = (info){,,i};
cnt++;
}
if (!DLX.solve()) printf("No solution\n");
else
{
memset(ans,,sizeof(ans));
for (i = ; i < DLX.step; i++)
{
ans[R[DLX.ans[i]].pos].s = R[DLX.ans[i]].l;
ans[R[DLX.ans[i]].pos].e = R[DLX.ans[i]].r;
}
for (i = ; i <= N; i++) printf("%d %d\n",ans[i].s,ans[i].e);
}
printf("\n");
} return ; }