题意：

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; }