#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
#define sep ' '
#define F first
#define S second
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define kill(x) {cout << x << endl;return;}
#define sz(x) int(x.size())
#define SP(x) setprecision(x)
#define mod(x) (1ll*x%M+M)%M
#define pq priority_queue
#define mid (l+r)/2
// #define mid2 (l+r+1)/2
#define pll pair<ll, ll>
#define REP(i, k) for (int i = 0 ; i < k ; i ++)
#define MP make_pair
#define us unordered_set
#define int ll
const int INF = 1e9+10;
const int N = 1e3+10;
int n, m, q;
int d[N];
vi adj[N];
ll dy[N][N]; // drunk yes
ll dn[N][N]; // drunk no
ll nd[N][N]; // not drunk
ll ans[N], ans_dy[N], ans_dn[N], ans_nd[N];
bool vis[N];
int sz[N];
ll tmp;
void dfs(int v) {
vis[v] = true;
sz[v]++;
dy[v][0] = INF;
dn[v][0] = d[v];
nd[v][0] = 0;
for(int u: adj[v]) {
if (vis[u]) continue;
dfs(u);
sz[v] += sz[u];
for(int i = sz[v] ; i >= 0 ; i --) {
dy[v][i] = dy[v][0] + min({dy[u][i], nd[u][i], (i-1 < 0 ? INF : dn[u][i-1])});
dn[v][i] = dn[v][0] + nd[u][i];
nd[v][i] = nd[v][0] + min({nd[u][i], dn[u][i], dy[u][i]});
for(int j = 1 ; j <= min(i, sz[u]) ; j ++) {
dy[v][i] = min(dy[v][i], dy[v][j] + min({dy[u][i-j], nd[u][i-j], (i-j-1 < 0 ? INF : dn[u][i-j-1])}));
dn[v][i] = min(dn[v][i], dn[v][j] + nd[u][i-j]);
nd[v][i] = min(nd[v][i], nd[v][j] + min({nd[u][i-j], dn[u][i-j], dy[u][i-j]}));
}
}
}
}
void solve() {
cin >> n >> m;
REP(i, N) {
fill(dy[i], dy[i]+N, INF);
fill(dn[i], nd[i]+N, INF);
fill(nd[i], nd[i]+N, INF);
}
fill(ans, ans+N, INF);
fill(ans_dn, ans_dn+N, INF);
fill(ans_dy, ans_dy+N, INF);
fill(ans_nd, ans_nd+N, INF);
REP(i, n) cin >> d[i];
REP(i, m) {
int u, v; cin >> u >> v; u--, v--;
adj[u].pb(v), adj[v].pb(u);
}
int k = 0;
REP(u, n) {
if (!vis[u]) {
dfs(u);
REP(i, sz[u]) {
cout << i << sep << dy[u][i] << endl;
}
// k += sz[u];
// for(int i = k ; i >= 0 ; i --) {
// ans_dy[i] = ans_dy[0] + min({dy[u][i], nd[u][i], (i-1 < 0 ? INF : dn[u][i-1])});
// ans_dn[i] = ans_dn[0] + nd[u][i];
// ans_nd[i] = ans_nd[0] + min({nd[u][i], dn[u][i], dy[u][i]});
// for(int j = 1 ; j <= min(i, sz[u]) ; j ++) {
// ans_dy[i] = min(ans_dy[i], ans_dy[j] + min({dy[u][i-j], nd[u][i-j], (i-j-1 < 0 ? INF : dn[u][i-j-1])}));
// ans_dn[i] = min(ans_dn[i], ans_dn[j] + nd[u][i-j]);
// ans_nd[i] = min(ans_nd[i], ans_nd[j] + min({nd[u][i-j], dn[u][i-j], dy[u][i-j]}));
// }
// }
}
}
// REP(i, n) {
// ans[i] = min({ans_dy[i], ans_dn[i], ans_nd[i], INF});
// cout << ans[i] << sep;
// }
// cout << endl;
// cin >> q;
// while(q--) {
// int s; cin >> s;
// int res = upper_bound(ans, ans+n+1, s) - ans;
// cout << res << endl;
// }
}
// check MAXN
int32_t main() {
fastIO;
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |