#include <bits/stdc++.h>
#define maxN 105
#define maxV 505
using namespace std;
bool visited[maxV];
int n,m,c,k,i,j,x,y,ux[maxN],uy[maxN],sx[maxN],sy[maxN];
int rgraph[maxV][maxV];
int ans[maxN];
vector <int> v[maxN];
int dfs(int x,int n,int t,int mf){
visited[x]=true;
if(x==t) return mf;
for(int i=0;i<n;i++){
if(!visited[i] && rgraph[x][i]>0){
int tmp=dfs(i,n,t,min(mf,rgraph[x][i]));
if(tmp>0){
tmp=min(tmp,rgraph[x][i]);
rgraph[x][i]-=tmp;
rgraph[i][x]+=tmp;
return tmp;
}
}
}
return 0;
}
int maxflow(int n,int s,int t){
memset(visited,false,n+1);
int ans=0,tmp;
tmp=dfs(s,n,t,INT_MAX);
while(tmp){
ans+=tmp;
memset(visited,false,n+1);
tmp=dfs(s,n,t,INT_MAX);
}
return ans;
}
bool blizu(int d,int a,int b){
return (ux[a]-sx[b])*(ux[a]-sx[b])+(uy[a]-sy[b])*(uy[a]-sy[b])<=d;
}
bool resi(int x){
int i,j,t;
for(i=0;i<n+k+2;i++){
for(j=0;j<n+k+2;j++){
rgraph[i][j]=0;
}
}
for(i=1;i<=n;i++) rgraph[0][i]=1;
for(i=1;i<=n;i++){
for(j=n+1;j<=n+k;j++){
rgraph[i][j]=0;
for(t=0;t<v[j-n-1].size();t++){
if(blizu(x,i-1,v[j-n-1][t])) {rgraph[i][j]=1; break;}
}
}
}
for(i=n+1;i<=n+k;i++) rgraph[i][n+k+1]=c;
return n<=maxflow(n+k+2,0,n+k+1);
}
int nadji(int x,int a,int b){
for(int i=0;i<v[b].size();i++){
if(blizu(x,a,v[b][i])) return v[b][i]+1;
}
}
void resi2(int x){
int i,j,t,graph[maxV][maxV];
for(i=0;i<n+k+2;i++){
for(j=0;j<n+k+2;j++){
graph[i][j]=rgraph[i][j]=0;
}
}
for(i=1;i<=n;i++) {graph[0][i]=1; rgraph[0][i]=1;}
for(i=1;i<=n;i++){
for(j=n+1;j<=n+k;j++){
graph[i][j]=0;
for(t=0;t<v[j-n-1].size();t++){
if(blizu(x,i-1,v[j-n-1][t])) {graph[i][j]=1; break;}
}
rgraph[i][j]=graph[i][j];
}
}
for(i=n+1;i<=n+k;i++) {graph[i][n+k+1]=c; rgraph[i][n+k+1]=c;}
maxflow(n+k+2,0,n+k+1);
for(i=1;i<=n;i++){
for(j=n+1;j<=n+k;j++){
if(rgraph[i][j]<graph[i][j]){
ans[i-1]=nadji(x,i-1,j-n-1);
break;
}
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin>>n>>m>>c>>k;
for(i=0;i<n;i++) cin>>ux[i]>>uy[i];
for(i=0;i<m;i++) cin>>sx[i]>>sy[i];
for(i=0;i<k;i++){
cin>>x;
for(j=0;j<x;j++){
cin>>y;
v[i].push_back(y-1);
}
}
int l,d,m;
l=0;
d=10000000;
while(d>l){
m=(l+d)/2;
if(resi(m)) d=m;
else l=m+1;
}
if(l==10000000) {cout<<-1<<endl; return 0;}
cout<<l<<endl;
resi2(l);
for(i=0;i<n;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
Compilation message
priglvaci.cpp: In function 'bool resi(int)':
priglvaci.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(t=0;t<v[j-n-1].size();t++){
~^~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'int nadji(int, int, int)':
priglvaci.cpp:67:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[b].size();i++){
~^~~~~~~~~~~~
priglvaci.cpp: In function 'void resi2(int)':
priglvaci.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(t=0;t<v[j-n-1].size();t++){
~^~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'int nadji(int, int, int)':
priglvaci.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
24 ms |
1184 KB |
Output is correct |
| 5 |
Correct |
22 ms |
1184 KB |
Output is correct |
| 6 |
Correct |
39 ms |
1348 KB |
Output is correct |
| 7 |
Correct |
31 ms |
1348 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1348 KB |
Output is correct |
| 9 |
Correct |
38 ms |
1348 KB |
Output is correct |
| 10 |
Correct |
29 ms |
1348 KB |
Output is correct |
