• Source 
    1. #include <cstdio>
    2. #include <cstring>
    3. #include <algorithm>
    4. #include <iostream>
    5. #include <map>
    6. #include <vector>
    7. #include <queue>
    8. //  by zrt
    9. //  problem:
    10. //  无论你在什么时候开始，重要的是开始以后就不要停止。
    11. using namespace std ;
    12. typedef long long LL ;
    13. const double eps(1e-10) ;
    14. const int inf(0x3f3f3f3f) ;
    15. map<string,int> mp;
    16. int S,T;
    17. string s,u,v;
    18. int num;
    19. int n,m;
    20. int limited;
    21. int tima[5006],timb[5006],cap[5006];
    22. vector<int> in[160],out[160];
    23. int H[12000],X[5000000],P[5000000],tot,flow[5000000];
    24. inline void add(int x,int y,int z){
    25. 	P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
    26. }
    27. int d[12000];
    28. queue<int> q;
    29. bool bfs(){
    30. 	memset(d,0,sizeof d);
    31. 	d[S]=1;q.push(S);int x;
    32. 	while(!q.empty()){
    33. 		x=q.front();q.pop();
    34. 		for(int i=H[x];i;i=X[i]){
    35. 			if(flow[i]>0&&!d[P[i]]){
    36. 				d[P[i]]=d[x]+1;
    37. 				q.push(P[i]);
    38. 			}
    39. 		}
    40. 	}
    41. 	return d[T];
    42. }
    43. int dfs(int x,int a){
    44. 	if(x==T||a==0) return a;
    45. 	int f=a,tmp;
    46. 	for(int i=H[x];i;i=X[i]){
    47. 		if(flow[i]>0&&d[P[i]]==d[x]+1){
    48. 			tmp=dfs(P[i],min(flow[i],a));
    49. 			a-=tmp;
    50. 			flow[i]-=tmp;
    51. 			flow[i^1]+=tmp;
    52. 			if(!a) break;
    53. 		}
    54. 	}
    55. 	if(f==a) d[x]=-1;
    56. 	return f-a;
    57. }
    58. int Dinic(){
    59. 	int f(0);
    60. 	while(bfs()) f+=dfs(S,inf);
    61. 	return f;
    62. }
    63. int main(){
    64. 	#ifdef LOCAL
    65. 	freopen("in.txt","r",stdin) ;
    66. 	freopen("out.txt","w",stdout) ;
    67. 	#endif
    68. 	S=11000,T=11111;
    69. 	while(~scanf("%d",&n)){
    70. 		tot=1,memset(H,0,sizeof H);num=3;
    71. 		for(int i=0;i<=n;i++) in[i].clear(),out[i].clear();
    72. 		mp.clear();
    73. 		cin>>s;
    74. 		mp[s]=1;
    75. 		cin>>s;
    76. 		mp[s]=2;
    77. 		scanf("%d",&limited);
    78. 		limited=(limited%100)+(limited/100)*60;
    79. 		scanf("%d",&m);
    80. 		for(int i=0;i<m;i++){
    81. 			cin>>u>>v;
    82. 			if(mp.find(u)==mp.end()) mp[u]=num++;
    83. 			if(mp.find(v)==mp.end()) mp[v]=num++;
    84. 			scanf("%d%d%d",&cap[i],&tima[i],&timb[i]);
    85. 			tima[i]=(tima[i]%100)+(tima[i]/100)*60;
    86. 			timb[i]=(timb[i]%100)+(timb[i]/100)*60;
    87. 			out[mp[u]].push_back(i);in[mp[v]].push_back(i);
    88. 			if(timb[i]<=limited) add(i,i+m,cap[i]),add(i+m,i,0);
    89. 		}
    90. 		for(int i=0;i<out[1].size();i++){
    91. 			add(S,out[1][i],inf);
    92. 			add(out[1][i],S,0);
    93. 		}
    94. 		for(int i=0;i<in[2].size();i++){
    95. 			add(in[2][i]+m,T,inf);
    96. 			add(T,in[2][i]+m,0);
    97. 		}
    98. 		for(int i=1;i<=n;i++){
    99. 			for(int j=0;j<in[i].size();j++){
    100. 				for(int k=0;k<out[i].size();k++){
    101. 					if(tima[out[i][k]]-timb[in[i][j]]>=30&&tima[out[i][k]]<=limited){
    102. 						add(in[i][j]+m,out[i][k],inf);
    103. 						add(out[i][k],in[i][j]+m,0);
    104. 					}
    105. 				}
    106. 			}
    107. 		}
    108. 		printf("%d\n",Dinic());
    109. 	}
    110. 	return 0 ;
    111. }
    112.