题意:
有N个点,每个点上有K只青蛙。每个点有限制起跳次数。问那些点青蛙们可以作为相聚地点
解法:
拆点,然后在两个分点中加入限制条件
代码:
1
# include <cstdio>
2
# include <cstring>
3
# include <cmath>
4
# include <vector>
5
using namespace std;
6
int n;
7
double d;
8
vector<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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct edge
{ int x, y, nxt; typec c; } bf[E];
15
int ne, head[N], cur[N], ps[N], dep[N];
16
void init()
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
18
ne=0;
19
memset(head,-1,sizeof(head));
20
}
21
void addedge(int x, int y, typec c)
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{ // 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
}
28
typec flow(int n, int s, int t)
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
30
typec tr, res = 0;
31
int i, j, k, f, r, top;
32
while (1)
33![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
38
if (bf[j].c && -1 == dep[k = bf[j].y])
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
40
dep[k] = dep[i] + 1; ps[r++] = k;
41
if (k == t)
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
49
if (i == t)
50![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
62
ps[top++] = cur[i];
63
i = bf[cur[i]].y;
64
}
65
else
66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
67
if (0 == top) break;
68
dep[i] = -1; i = bf[ps[--top]].x;
69
}
70
}
71
}
72
return res;
73
}
74![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
75![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
76
struct node
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
78
double x,y;
79
int num,maxt;
80
}data[101];
81
int main()
82![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
83
//freopen("ans.txt","w",stdout);
84
int test;
85
scanf("%d",&test);
86
while(test--)
87![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
88
int totalnum=0;
89
ans.clear();
90
scanf("%d%lf",&n,&d);
91
for(int i=0;i<n;i++)
92![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
98
init();
99
for(int i=0;i<n;i++)
100![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
127![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)