首页 > ACM题库 > HDU-杭电 > HDU 3663-Power Stations[解题报告]HOJ
2014
11-30

HDU 3663-Power Stations[解题报告]HOJ

Power Stations

问题描述 :

There are N towns in our country, and some of them are connected by electricity cables. It is known that every town owns a power station. When a town’s power station begins to work, it will provide electric power for this town and the neighboring towns which are connected by cables directly to this town. However, there are some strange bugs in the electric system �One town can only receive electric power from no more than one power station, otherwise the cables will be burned out for overload.

The power stations cannot work all the time. For each station there is an available time range. For example, the power station located on Town 1 may be available from the third day to the fifth day, while the power station on Town 2 may be available from the first day to the forth day. You can choose a sub-range of the available range as the working time for each station. Note that you can only choose one sub-range for each available range, that is, once the station stops working, you cannot restart it again. Of course, it is possible not to use any of them.

Now you are given all the information about the cable connection between the towns, and all the power stations’ available time. You need to find out a schedule that every town will get the electricity supply for next D days, one and only one supplier for one town at any time.

输入:

There are several test cases. The first line of each test case contains three integers, N, M and D (1 <= N <= 60, 1 <= M <= 150, 1 <= D <= 5), indicating the number of towns is N, the number of cables is M, and you should plan for the next D days.

Each of the next M lines contains two integers a, b (1 <= a, b <= N), which means that Town a and Town b are connected directly. Then N lines followed, each contains two numbers si and ei, (1 <= si <= ei <= D) indicating that the available time of Town i’s power station is from the si-th day to the ei-th day (inclusive).

输出:

There are several test cases. The first line of each test case contains three integers, N, M and D (1 <= N <= 60, 1 <= M <= 150, 1 <= D <= 5), indicating the number of towns is N, the number of cables is M, and you should plan for the next D days.

Each of the next M lines contains two integers a, b (1 <= a, b <= N), which means that Town a and Town b are connected directly. Then N lines followed, each contains two numbers si and ei, (1 <= si <= ei <= D) indicating that the available time of Town i’s power station is from the si-th day to the ei-th day (inclusive).

样例输入:

3 3 5
1 2
2 3
3 1
1 5
1 5
1 5

4 4 5
1 2
2 3
3 4
4 1
1 5
1 5
1 5
1 5

样例输出:

1 5
0 0
0 0

No solution

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define maxn 1010
#define max_node 500010
#define inf 0xfffffff
int total;
int R[max_node];
int L[max_node];
int U[max_node];
int D[max_node];
int col[max_node];
int row[max_node];
int h[maxn];
int s[maxn];
int ans[maxn];
void initDL(int c)
{
	memset(h,-1,sizeof(h));
	memset(s,0,sizeof(s));
	for(int i=0;i<=c;i++)
	{
		D[i]=U[i]=i;
		L[i+1]=i;
		R[i]=i+1;
	}
	R[c]=0;
	total=c+1;
}
void link(int r,int c)
{
	s[c]++;
	row[total]=r;
	col[total]=c;
	U[total]=U[c];
	D[U[c]]=total;
	D[total]=c;
	U[c]=total;
	if(h[r] == -1)
		h[r]=L[total]=R[total]=total;
	else
	{
		L[total]=L[h[r]];
		R[L[h[r]]]=total;
		R[total]=h[r];
		L[h[r]]=total;
	}
	total++;
}
void remove(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(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;
}
struct Node
{
	int id;
	int begin,end;
	Node(){}
	Node(int id0,int begin0,int end0):id(id0),begin(begin0),end(end0){}
}p[1010];
pair<int,int>out[1010];
int n,m,d;
bool dance(int dep)
{
	if(R[0] == 0 || R[0] > n*d)
	{
		for(int i=0;i<n;i++)
			out[i]=make_pair(0,0);
		for(int i=0;i<dep;i++)
		{
			int id=p[ans[i]].id;
			int begin=p[ans[i]].begin;
			int end=p[ans[i]].end;
			out[id]=make_pair(begin+1,end+1);
		}
		return true;
	}
	int mm=inf;
	int c;
	for(int i=R[0];i;i=R[i])
		if(i <= n*d && s[i] < mm)
		{
			mm=s[i];
			c=i;
		}
	remove(c);
	for(int i=D[c];i!=c;i=D[i])
	{
		ans[dep]=row[i];
		for(int j=R[i];j!=i;j=R[j])
			remove(col[j]);
		if(dance(dep+1))
			return true;
		for(int j=L[i];j!=i;j=L[j])
			resume(col[j]);
	}
	resume(c);
	return false;
}
struct Edge
{
	int v,next;
}edge[100010];
int head[1010];
int pos;
void insert(int x,int y)
{
	edge[pos].v=y;
	edge[pos].next=head[x];
	head[x]=pos++;
}
bool g[1010][1010];
int main()
{
	while(scanf("%d %d %d",&n,&m,&d)!=EOF)
	{
		memset(head,0,sizeof(head));
		pos=1;
		while(m--)
		{
			int x,y;
			scanf("%d %d",&x,&y);
			x--;
			y--;
			insert(x,y);
			insert(y,x);
		}
		initDL(n*d+n);
		memset(g,false,sizeof(g));
		int r=0;
		for(int l=0;l<n;l++)
		{
			int begin,end;
			scanf("%d %d",&begin,&end);
			begin--;
			end--;
			for(int a=begin;a<=end;a++)
				for(int b=a;b<=end;b++)
				{
					g[r][n*d+l]=true;
					for(int i=a;i<=b;i++)
						g[r][n*i+l]=true;
					for(int t=head[l];t;t=edge[t].next)
					{
						int v=edge[t].v;
						for(int i=a;i<=b;i++)
							g[r][n*i+v]=true;
					}
					p[++r]=Node(l,a,b);
				}
		}
		for(int i=0;i<r;i++)
			for(int j=0;j<n*d+n;j++)
				if(g[i][j])
					link(i+1,j+1);
		if(!dance(0))
			printf("No solution\n");
		else
		{
			for(int i=0;i<n;i++)
				printf("%d %d\n",out[i].first,out[i].second);
		}
		printf("\n");
	}
	return 0;
}

  1. [email protected]

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  3. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }