程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NOJ 1548 hash+網絡流

NOJ 1548 hash+網絡流

編輯:C++入門知識

 

題意:

1、每種書在圖書館裡有且僅有一本。

2、每個人閱讀一本書需要一天。

3、當一個人閱讀完一本書後會使社會幸福感增加1.

4、自然,當好孩子看完書後一大早就歸還圖書館,不會影響第二天借書。

第一行給出n,m,K(1<=n,m<=100, 1<=K<=10)表示有n個人(編號從1-n),圖書館藏書m本(編號從1-m)。

下面n行第i行表示第i個人的借書情況,先給出兩個整數 S, P(1<=S,P<=100)表示第i個人的借閱時間從第S天開始借閱(借閱時間是[S,S+K-1]),對P本書感興趣,後面P個數字代表所感興趣的書。

輸出一個整數表示能增加的最大社會幸福感,若不能使社會更幸福就輸出”If you do not leave me, I will by your side until the life end!”(不包括引號)

 

思路:

首先可以確定是網絡流。

人、書、時間三者互相約束,一天內一本書只能被一個人讀。如果直接將三者hash 點數最大是n^3*k。

所以將其中兩者hash出,最大點數可以降到n^2*k,而這個方法要注意在中間的因素要進行拆點,類似以下數據可以cha掉未拆點的代碼:

3 3 2
1 2 2 3
2 2 2 3
2 2 2 3

 

建圖:

將人+書 的所有狀態hash出來,和源點建邊,權值為1

將人+時間的狀態拆點,對應建邊,權值為1

將人+時間一端連向人+書,權值為1,另一端連向時間+書,權值為1

將時間+書連向匯點,權值為1

標程:

#include
#include
#include
#include
#include
using namespace std;

#define N 100000
#define M 1000000
#define inf 536870912
#define end End
inline int max(int a,int b){return a>b?a:b;}
struct Edge{
	int from, to, cap, nex;
}edge[M];

int head[N], edgenum;
void addedge(int u, int v, int cap){
	Edge E = { u, v, cap, head[u]};
	edge[ edgenum ] = E;
	head[u] = edgenum ++;

	Edge E2= { v, u, 0,   head[v]};
	edge[ edgenum ] = E2;
	head[v] = edgenum ++;
}
int sign[N], s, t;
bool BFS(int from, int to){
	memset(sign, -1, sizeof(sign));
	sign[from] = 0;

	queueq;
	q.push(from);
	while( !q.empty() ){
		int u = q.front(); q.pop();
		for(int i = head[u]; i!=-1; i = edge[i].nex)
		{
			int v = edge[i].to;
			if(sign[v]==-1 && edge[i].cap)
			{
				sign[v] = sign[u] + 1, q.push(v);
				if(sign[to] != -1)return true;
			}
		}
	}
	return false;
}
int Stack[M], top, cur[M];
int dinic(){

	int ans = 0, i;
	while( BFS(s, t) )
	{
		memcpy(cur, head, sizeof(head));
		int u = s;		top = 0;
		while(1)
		{
			if(u == t)
			{
				int flow = inf, loc;
				for(i = 0; i < top; i++)
					if(flow > edge[ Stack[i] ].cap)
					{
						flow = edge[Stack[i]].cap;
						loc = i;
					}

					for(i = 0; i < top; i++)
					{
						edge[ Stack[i] ].cap -= flow;
						edge[Stack[i]^1].cap += flow;
					}
					ans += flow;
					top = loc;
					u = edge[Stack[top]].from;
			}
			for(i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)
				if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;
			if(cur[u] != -1)
			{
				Stack[top++] = cur[u];
				u = edge[ cur[u] ].to;
			}
			else
			{
				if( top == 0 )break;
				sign[u] = -1;
				u = edge[ Stack[--top] ].from;
			}
		}
	}
	return ans;
}
int n, m, K;
int from[101], lastday;
vectorG[101];
int idxpre1(int peo, int day){ return day+K*(peo-1);}
int idxpre2(int peo, int day){ return day+K*(peo-1)+n*K+m*lastday+m*n;}
int idxbook(int book, int day){	return book+m*(day-1)+n*K;}
int idxpre_book(int peo, int book){	return book+m*(peo-1)+n*K+m*lastday;}
void init(){
	memset(head, -1, sizeof(head)); edgenum = 0;
	for(int i = 1; i <= n; i++)G[i].clear();
	s = 0;
}
int main(){
	int i, j, k;
	while(~scanf(%d %d %d, &n, &m, &K)){
		init();
		for(i = 1; i <= n; i++)
		{
			scanf(%d,&from[i]); scanf(%d,&j);
			while(j--){ int t;scanf(%d,&t); G[i].push_back(t); }
		}
		lastday = 0;
		for(i = 1; i <= n; i++)lastday = max(lastday, from[i]);
		lastday += (K-1);
		t = idxpre2(n, m) +1;
		for(i = 1; i <= n; i++)
			for(j = 0; j < G[i].size(); j++)
			{
				addedge(s, idxpre_book(i, G[i][j]), 1); //源點-人+書
				for(k = 1; k <= K; k++)
					addedge(idxpre_book(i, G[i][j]), idxpre1(i, k), 1);//人+書 - 人+時間
			}
		for(i = 1; i <= n; i++)
			for(k = 1; k <= K; k++)
					addedge(idxpre1(i, k), idxpre2(i, k), 1);//人+時間1 - 人+時間2

		for(i = 1; i <= n; i++)
			for(k = 1; k <= K; k++)
				for(j = 0; j < G[i].size(); j++)
					addedge(idxpre2(i, k), idxbook(G[i][j], from[i]+k-1), 1);//人+時間2 - 時間+書

		for(i = 1; i <= lastday; i++)
			for(j = 1; j <= m; j++)
				addedge(idxbook(j, i), t, 1);//時間+書 - 匯點

		printf(%d
, dinic());
	}
	return 0;	
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved