这个题目一直以为是要用图论知识来做，可是一点建图的思绪都没有，后来知道暴力便可破之。由于牛的产奶周期最大为10，1.2.3.....10的最小公倍数是MT = 2520，所以把MT作为最大的周期，然后枚举这个周期内的每一天，看产奶量最小的牛是否唯一，然后杀掉是唯一的最少产奶的那头牛，知道遇到一个周期内没有牛被杀掉。这样就到达了一个稳定的最终状态，统计剩下的牛，和杀掉最后一头牛用去的时间。注意一头牛都不杀的情况应该输出天数为0.
不过这题还有更加标准的做法，刘汝佳黑书中提到，将周期相同的奶牛产奶情况用一个堆来维护，每次用一个最小的代表去和其他周期的奶牛比较。删除操作效率比较高。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <climits> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cmath> 7 #include <vector> 8 #include <queue> 9 #include <algorithm> 10 #define esp 1e-6 11 #define pb push_back 12 #define in freopen("in.txt", "r", stdin); 13 #define out freopen("out.txt", "w", stdout); 14 #define print(a) printf("%d ",(a)); 15 #define bug puts("********))))))"); 16 #define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++) 17 #define inf 0x0f0f0f0f 18 using namespace std; 19 typedef long long LL; 20 typedef vector<int> VI; 21 typedef vector<int>:: iterator IT; 22 typedef pair<int, int> pii; 23 #define N 2000 24 #define M 30 25 #define MT 2520 26 int vis[N], a[N][M], T[N], num[N]; 27 int n; 28 int main(void) 29 { 30 int t; 31 scanf("%d", &t); 32 while(t--) 33 { 34 memset(vis, 0, sizeof(vis)); 35 for(int i = scanf("%d", &n) - 1 ; i < n; i++) 36 { 37 for(int j = scanf("%d", T + i) - 1; j < T[i]; j++) 38 scanf("%d", &a[i][j]); 39 } 40 int nT = 0, nNum = n, nDay = 0, last, temp, k; 41 while(1) 42 { 43 int Min,j; 44 temp = 0; 45 for(int i = 0; i < MT; i++) 46 { 47 memset(num, 0, sizeof(num)); 48 for(j = 0, k = -1, Min = inf; j < n; j++) 49 if(!vis[j]) 50 { 51 if(Min == a[j][i % T[j]]) 52 { 53 num[k]++; 54 } 55 else if(Min > a[j][i % T[j]]) 56 { 57 Min = a[j][i % T[j]]; 58 k = j; 59 num[j]++; 60 } 61 } 62 if(k >= 0 && num[k] == 1) 63 { 64 temp++; 65 vis[k] = 1; 66 nNum--; 67 last = i; 68 } 69 } 70 if(temp) 71 { 72 if(nT) 73 nDay += MT; 74 } 75 else 76 { 77 if(nT) 78 nDay += last + 1; 79 break; 80 } 81 nT++; 82 } 83 printf("%d %d ", nNum, nDay); 84 } 85 return 0; 86 }