tarjan缩点，然后树形dp一下可解。重点是重边的处理。
/* 2242 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct {
int v, nxt;
} edge_t; const int maxv = ;
const int maxe = ;
int head[maxv], l;
edge_t E[maxe];
int low[maxv], pre[maxv], bn[maxv];
int S[maxv], top;
int block, dfs_clock;
int num[maxv], tot[maxv], sum;
int head_[maxv], l_;
edge_t E_[maxe];
bool visit[maxv];
int n, m;
int ans; void init() {
l = block = dfs_clock = ;
top = ;
memset(pre, , sizeof(pre));
memset(bn, , sizeof(bn));
memset(head, -, sizeof(head));
} void init_() {
l_ = sum = ;
memset(tot, , sizeof(tot));
memset(head_, -, sizeof(head_));
memset(visit, false, sizeof(visit));
ans = INT_MAX;
} void addEdge(int u, int v) {
E[l].v = v;
E[l].nxt = head[u];
head[u] = l++; E[l].v = u;
E[l].nxt = head[v];
head[v] = l++;
} void addEdge_(int u, int v) {
E_[l_].v = v;
E_[l_].nxt = head_[u];
head_[u] = l_++; E_[l_].v = u;
E_[l_].nxt = head_[v];
head_[v] = l_++;
} void tarjan(int u, int fa) {
int v, k;
bool flag = true; S[top++] = u;
pre[u] = low[u] = ++dfs_clock;
for (k=head[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (v == fa && flag) {
flag = false;
continue;
} if (!pre[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
} else if (!bn[v]) {
low[u] = min(low[u], pre[v]);
}
} if (low[u] == pre[u]) {
++block;
do {
bn[S[--top]] = block;
} while (S[top]!=u);
}
} void dfs(int u, int fa) {
int v, k; visit[u] = true;
for (k=head_[u]; k!=-; k=E_[k].nxt) {
v = E_[k].v;
if (v==fa || visit[v])
continue;
dfs(v, u);
tot[u] += tot[v];
} ans = min(ans, abs(sum-tot[u]-tot[u]));
} void solve() {
rep(i, , n) {
if (!pre[i])
tarjan(i, -);
} #ifndef ONLINE_JUDGE
printf("block = %d\n", block);
#endif if (block <= ) {
puts("impossible");
return ;
} init_();
int u, v, k; for (u=; u<n; ++u) {
tot[bn[u]] += num[u];
sum += num[u];
for (k=head[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (bn[v] != bn[u]) {
addEdge_(bn[u], bn[v]);
}
}
} dfs(, -);
printf("%d\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int u, v; while (scanf("%d %d", &n, &m)!=EOF) {
rep(i, , n)
scanf("%d", &num[i]);
init();
rep(i, , m) {
scanf("%d %d", &u, &v);
addEdge(u, v);
}
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
数据生成器。
import sys
import string
from random import randint def GenData(fileName):
with open(fileName, "w") as fout:
t = 10
for tt in xrange(t):
n = randint(100, 200)
m = randint(n/10, n+n/10)
fout.write("%d %d\n" % (n, m))
dataList = []
for i in xrange(n):
x = randint(0, 1000)
dataList.append(x)
fout.write(" ".join(map(str, dataList)) + "\n")
for i in xrange(m):
a = randint(0, n)
b = randint(0, n)
fout.write("%d %d\n" % (a, b)) def MovData(srcFileName, desFileName):
with open(srcFileName, "r") as fin:
lines = fin.readlines()
with open(desFileName, "w") as fout:
fout.write("".join(lines)) def CompData():
print "comp"
srcFileName = "F:\Qt_prj\hdoj\data.out"
desFileName = "F:\workspace\cpp_hdoj\data.out"
srcLines = []
desLines = []
with open(srcFileName, "r") as fin:
srcLines = fin.readlines()
with open(desFileName, "r") as fin:
desLines = fin.readlines()
n = min(len(srcLines), len(desLines))-1
for i in xrange(n):
ans2 = int(desLines[i])
ans1 = int(srcLines[i])
if ans1 > ans2:
print "%d: wrong" % i if __name__ == "__main__":
srcFileName = "F:\Qt_prj\hdoj\data.in"
desFileName = "F:\workspace\cpp_hdoj\data.in"
GenData(srcFileName)
MovData(srcFileName, desFileName)