題意：
有N個(gè)點(diǎn)，每個(gè)點(diǎn)上有K只青蛙。每個(gè)點(diǎn)有限制起跳次數(shù)。問(wèn)那些點(diǎn)青蛙們可以作為相聚地點(diǎn)
解法：
拆點(diǎn)，然后在兩個(gè)分點(diǎn)中加入限制條件
代碼：
1
# include <cstdio>
2# include <cstring>
3# include <cmath>
4# include <vector>
5using namespace std;
6int n;
7double d;
8vector<int> ans;
9# define le(a,b) (fabs((a)-(b))<1e-6||(a)<(b))
10# define typec int // type of cost
11# define inf 0xfffffff // max of cost
12# define E 30000
13# define N 300
14
struct edge 
{ int x, y, nxt; typec c; } bf[E];
15int ne, head[N], cur[N], ps[N], dep[N];
16void init()
17{
18
ne=0;
19 memset(head,-1,sizeof(head));
20
}
21void addedge(int x, int y, typec c)
22{ // add an arc(x -> y, c); vertex: 0 ~ n-1;
23 bf[ne].x = x; bf[ne].y = y; bf[ne].c = c;
24 bf[ne].nxt = head[x]; head[x] = ne++;
25 bf[ne].x = y; bf[ne].y = x; bf[ne].c = 0;
26 bf[ne].nxt = head[y]; head[y] = ne++;
27}
28typec flow(int n, int s, int t)
29{
30 typec tr, res = 0;
31 int i, j, k, f, r, top;
32 while (1)
33
{
34 memset(dep, -1, n * sizeof(int));
35 for (f = dep[ps[0] = s] = 0, r = 1; f != r; )
36 for (i = ps[f++], j = head[i]; j!=-1; j = bf[j].nxt)
37 {
38 if (bf[j].c && -1 == dep[k = bf[j].y])
39 {
40 dep[k] = dep[i] + 1; ps[r++] = k;
41 if (k == t)
42 { f = r; break; }
43
}
44 }
45 if (-1 == dep[t]) break;
46 memcpy(cur, head, n * sizeof(int));
47 for (i = s, top = 0; ; )
48 {
49 if (i == t)
50 {
51 for (k = 0, tr = inf; k < top; ++k)
52 if (bf[ps[k]].c < tr)
53 tr = bf[ps[f = k]].c;
54 for (k = 0; k < top; ++k)
55 bf[ps[k]].c -= tr, bf[ps[k]^1].c += tr;
56 res += tr; i = bf[ps[top = f]].x;
57 }
58 for (j=cur[i]; cur[i] != -1; j = cur[i] = bf[cur[i]].nxt)
59 if (bf[j].c && dep[i]+1 == dep[bf[j].y]) break;
60 if (cur[i] != -1)
61 {
62 ps[top++] = cur[i];
63 i = bf[cur[i]].y;
64 }
65 else
66 {
67 if (0 == top) break;
68 dep[i] = -1; i = bf[ps[--top]].x;
69 }
70 }
71 }
72 return res;
73}
74
75
76struct node
77{
78 double x,y;
79 int num,maxt;
80}data[101];
81int main()
82{
83 //freopen("ans.txt","w",stdout);
84 int test;
85 scanf("%d",&test);
86 while(test--)
87 {
88 int totalnum=0;
89 ans.clear();
90 scanf("%d%lf",&n,&d);
91 for(int i=0;i<n;i++)
92 {
93 scanf("%lf%lf%d%d",&data[i].x,&data[i].y,&data[i].num,&data[i].maxt);
94 totalnum+=data[i].num;
95 }
96 for(int target=0;target<n;target++)
97 {
98 init();
99 for(int i=0;i<n;i++)
100 {
101 addedge(0,2*i+1,data[i].num);
102 addedge(2*i+1,2*i+2,data[i].maxt);
103 for(int j=0;j<i;j++)
104 if(le((data[i].x-data[j].x)*(data[i].x-data[j].x)+(data[i].y-data[j].y)*(data[i].y-data[j].y),d*d))
105 {
106 // printf("%d,%d\n",i,j);
107 addedge(2*i+2,2*j+1,inf);
108 addedge(2*j+2,2*i+1,inf);
109 }
110 }
111 int tt=flow(2*n+1,0,2*target+1);
112 if(tt==totalnum)
113 ans.push_back(target);
114 }
115 if(ans.empty()) printf("-1\n");
116 else
117 {
118 printf("%d",ans[0]);
119 for(int i=1;i<ans.size();i++)
120 printf(" %d",ans[i]);
121 printf("\n");
122 }
123 }
124 return 0;
125}
126
127