#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)
// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
advance(it, -n);
return it;
}
template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
advance(it, n);
return it;
}
#endif
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
template<typename T>
inline T sq(T a) { return a * a; }
//#ifdef LOCAL_MACHINE
//#endif
const int MAXN = 105;
const int NODES = 3 * MAXN;
int ux[MAXN], uy[MAXN], sx[MAXN], sy[MAXN];
int stop[MAXN];
// max flow start
int cap[NODES][NODES], p[NODES];
bool visit[NODES];
vi adj[NODES];
bool bfs(int s, int t) {
memset(p, -1, sizeof p);
memset(visit, false, sizeof visit);
queue<int> q;
q.push(s);
visit[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == t) break;
for (auto v : adj[u]) {
if (cap[u][v] > 0 && !visit[v]) {
p[v] = u;
visit[v] = true;
q.push(v);
}
}
}
return visit[t];
}
const int INF = 1e9;
int EdmondsKarp(int s, int t) {
int mf = 0;
while (bfs(s, t)) {
int f = INF;
for (int u = t; u != s; u = p[u])
f = min(f, cap[p[u]][u]);
for (int u = t; u != s; u = p[u]) {
cap[p[u]][u] -= f;
cap[u][p[u]] += f;
}
//if (f == 0) break;
mf += f;
}
return mf;
}
void addEdge(int u, int v, int c) {
//printf("edge (%d, %d, %d)\n", u, v, c);
adj[u].pb(v);
adj[v].pb(u);
cap[u][v] = c;
}
// max flow end
int main() {
//freopen("", "r", stdin);
//freopen("", "w", stdout);
int n, m, c, k;
scanf("%d %d %d %d", &n, &m, &c, &k);
for (int i = 1; i <= n; i++)
scanf("%d %d", &ux[i], &uy[i]);
for (int i = 1; i <= m; i++)
scanf("%d %d", &sx[i], &sy[i]);
for (int i = 1; i <= k; i++) {
int len;
scanf("%d", &len);
while (len--) {
int x;
scanf("%d", &x);
stop[x] = i;
}
}
vector<pair<int, ii> > edg;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int dist = sq(ux[i] - sx[j]) + sq(uy[i] - sy[j]);
edg.pb(mp(dist, mp(i, j)));
}
}
sort(all(edg));
const int s = 0, t = n + m + k + 1;
for (int i = 1; i <= n; i++)
addEdge(s, i, 1);
for (int j = 1; j <= m; j++)
addEdge(n + j, n + m + stop[j], c);
for (int z = 1; z <= k; z++)
addEdge(n + m + z, t, c);
int ans = 0, cur = 0;
bool found = false;
for (int e = 0, nxt; e < (int)edg.size(); e = nxt) {
nxt = e;
do {
addEdge(edg[nxt].se.fi, n + edg[nxt].se.se, 1);
ans = edg[nxt].fi;
nxt++;
} while (nxt < (int)edg.size() && edg[nxt].fi == edg[nxt - 1].fi);
cur += EdmondsKarp(s, t);
//printf("%d) cur = %d\n", e, cur);
if (cur >= n) {
found = true;
break;
}
}
if (found) {
printf("%d\n", ans);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (cap[n + j][i] > 0)
printf("%d\n", j);
}
} else
puts("-1");
return 0;
}
Compilation message
priglvaci.cpp: In function 'int main()':
priglvaci.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &n, &m, &c, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ux[i], &uy[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &sx[i], &sy[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &len);
~~~~~^~~~~~~~~~~~
priglvaci.cpp:129:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
3 ms |
760 KB |
Output is correct |
| 3 |
Correct |
56 ms |
940 KB |
Output is correct |
| 4 |
Correct |
4 ms |
992 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1036 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1036 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1036 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1036 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1072 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1148 KB |
Output is correct |
