hdu 3663 精确覆盖 dlx
2011年9月19日 15:47
此文充数.去年哈尔滨的D,残念啊伤心.
一些城市,每个都有电厂,既为自己供电,同时又为直接相邻的城市供电,但是供电有时间限制,而且同一城市不能有两处供电来源.求一个方案.
现在来看还是比较清晰的精确覆盖,有了数独的经验就知道用行来记录结果,用列来避免碰撞,所以拿电厂和发电时间去匹配城市和天数.转化也还算好想,发电时间枚举区间即可,但是题目有个限制,最后方案中的每个电厂的发电时间不能是离散区间,所以要加几列碰撞,使得每个电厂只能选一个发电区间,还要加一个发电区间表示电厂不发电,这几个点不太好想.转化好最后套进模板就出来了(我的模板的行列都是从1开始的,所以我把城市号处理成从0开始的了).
#include<cstdio>
#include<algorithm>
using namespace std;
#include<cstdlib>
#include<cstring>
bool mm[60][60];
int dd[60][2];
int q[16][2],top;
#define MAX 0x7fffffff
#define MAXR 4000
#define MAXC 700
bool arr[MAXR][MAXC];
#define SIZE MAXR*MAXC
int L[SIZE], R[SIZE], U[SIZE], D[SIZE],
Col[SIZE], Row[SIZE];//所在列 所在行
int S[MAXC]; //列元素数
int sel[MAXR],seln;//选择的行
struct Dancer
{
void init(int height,int width)
{
int p, x, y, last;
for (p = 1; p <= width; p++)
{
L[p] = p - 1; R[p] = p + 1;
U[p] = D[p] = p;
S[p] = 0;
}
p = width + 1;
for (y = 1; y <= height; y++)
{
last = R[0] = L[0] = 0;
for (x = 1; x <= width; x++)
{
if (arr[y][x] != 0)
{
L[p] = last; R[last] = p;
U[p] = U[x]; D[p] = x; U[x] = D[U[x]] = p;
Row[p]=y; Col[p]=x;
S[x]++; last=p++;
}
}
R[last] = R[0]; L[R[0]] = last;
}
R[width] = 0; L[0] = width; R[0] = 1;
S[0] = MAX;
}
void remove(const int &c)
{
L[R[c]] = L[c]; R[L[c]] = R[c];
for (int i = D[c]; i != c; 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 resume(const int &c)
{
for (int i = U[c]; i != c; i = U[i])
for (int j = L[i]; j != i; j = L[j])
{
U[D[j]] = j;
D[U[j]] = j;
++S[Col[j]];
}
L[R[c]] = c; R[L[c]] = c;
}
bool dance()
{
if (R[0] == 0) return true;
int c=0, i, j;
for (i = R[0]; i != 0; i = R[i])
if (S[i] < S[c]) c = i;
remove(c);
for (i = D[c]; i != c; i = D[i])
{
for (j = R[i]; j != i; j = R[j])
remove(Col[j]);
sel[seln]=Row[i];
seln++;
if (dance()) return true;
seln--;
for (j = L[i]; j != i; j = L[j])
resume(Col[j]);
}
resume(c); return false;
}
} dc;
/////////////////////////////////////////////////////////////
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int n,m,d;
while(scanf("%d%d%d",&n,&m,&d)!=EOF)
{
//all internals
top=1;
for(int i=1;i<=5;i++) for(int j=i;j<=5;j++)
q[top][0]=i,q[top++][1]=j;
memset(mm,false,sizeof(mm));
for(int i=0;i<n;i++) mm[i][i]=1;
for(int i=0;i<m;i++)
{
int a,b; scanf("%d%d",&a,&b);
a--;b--;
mm[a][b]=mm[b][a]=1;
}
for(int i=0;i<n;i++)
scanf("%d%d",&dd[i][0],&dd[i][1]);
//转化
memset(arr,false,sizeof(arr));
for(int i=0;i<n;i++)//each power station
{
for(int k=0;k<top;k++)//each internal
{
int r=i*top+k+1;//station i work on internal k
arr[r][n*d+i+1]=1;//station collision
int d1=q[k][0],d2=q[k][1];
if(k==0) continue;//not work
if(d1<dd[i][0] || d2>dd[i][1])//bad date
continue;
for(int j=0;j<n;j++) if(mm[i][j])//each city
for(int di=d1;di<=d2;di++)
{
int c=j*d+di;
arr[r][c]=1;//soga
}
}
}
//dance
seln=0; dc.init(n*top,n*d+n);
if(!dc.dance())
puts("No solution");
else
{
for(int i=0;i<seln;i++)//get data from line number
{
int s=(sel[i]-1)/top;//station
int k=(sel[i]-1)%top;
dd[s][0]=q[k][0]; dd[s][1]=q[k][1];//record
}
for(int i=0;i<n;i++)
printf("%d %d\n",dd[i][0],dd[i][1]);
}
putchar('\n');
}
}
