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; queue q; 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; vector G[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; }
