Description

Input

Output

Example

input

2
4 5
0 1 1 5
1 2
1 3
2 3
3 2
4 4
3 2
0 0 2
1 3
3 2

output

2
01001
0
01

题意

题目给你一个无向图，$n$个点，$m$条边，每个点带一个权值 a i a_i ai​，要求你给无向图的每一条边确定方向，使得 ∑ i = 1 n m a x ( 0 , d i − a i ) \sum_{i=1}^n{max(0,d_i-a_i)} ∑i=1n​max(0,di​−ai​)的值最小

思路

由$n,m$的范围可以得知这是一道网络流的题目
我们可以将原来连接$u,v$的两点拆成一个新的点$x$，拆分为$x$指向$u$容量为$1$，费用为$0$的有向边，以及$x$指向$v$容量为$1$，费用为$0$的有向边
然后将起点$S$连向每个$x$，容量为$1$费用为$0$（用于模拟当前边的指向）
每个$u$，$v$都连向终点$T$，由于当每个点的入度小于 a i a_i ai​时当前点的贡献都为$0$，大于 a i a_i ai​时每条多余的边贡献为$1$,所以分别为一条容量为 a i a_i ai​费用为$0$的有向边以及容量为$inf$费用为$1$的有向边指向终点$T$，建图思路大致如图，最后跑个最小费用最大流就好了

代码

#include 
#define ll long long
#define mem(s, i) memset(s, i, sizeof(s))
#define pb push_back
#define pii pair<int, int>
#define endl "\n"
using namespace std;
const int N = 1000 + 10;
const int M = 3e6 + 10;
const ll inf = 1e9;struct edge
{int to, next, cap, cos;
};edge e[M << 1];
int n, m, a[N], head[N << 1], cnt = 0, dis[N], vis[N], flow[N], pre[N], last[N], aa[N], bb[N];
int st, ed, maxflow = 0, mincost = 0;void add_edge(int u, int v, int cap, int cos)
{e[cnt].to = v, e[cnt].next = head[u], head[u] = cnt, e[cnt].cap = cap, e[cnt++].cos = cos;e[cnt].to = u, e[cnt].next = head[v], head[v] = cnt, e[cnt].cap = 0, e[cnt++].cos = -cos;
}bool spfa()
{queue<int> q;mem(dis, 0x3f);mem(vis, 0);vis[st] = 1, dis[st] = 0, flow[st] = inf;q.push(st);while (q.size()){int u = q.front();vis[u] = 0;q.pop();for (int i = head[u]; i != -1; i = e[i].next){int v = e[i].to;if (e[i].cap && dis[v] > dis[u] + e[i].cos){dis[v] = dis[u] + e[i].cos;flow[v] = min(flow[u], e[i].cap);pre[v] = u;last[v] = i;if (!vis[v]){vis[v] = 1;q.push(v);}}}}if (dis[ed] == 0x3f3f3f3f) return false;else return true;
}void MCMF()
{while (spfa()){int now = ed;maxflow += flow[ed];mincost += flow[ed] * dis[ed];while (now != st){e[last[now]].cap -= flow[ed];e[last[now] ^ 1].cap += flow[ed];now = pre[now];}}
}void solve()
{cin >> n >> m;maxflow = 0, mincost = 0;cnt = 0;mem(head, -1);for (int i = 1; i <= n; i++){cin >> a[i];}st = n + m + 1, ed = n + m + 2;for (int i = 1; i <= m; i++){cin >> aa[i] >> bb[i];add_edge(st, n + i, 1, 0);add_edge(n + i, aa[i], 1, 0);add_edge(n + i, bb[i], 1, 0);}for (int i = 1; i <= n; i++){add_edge(i, ed, a[i], 0);add_edge(i, ed, inf, 1);}MCMF();cout << mincost << endl;for (int i = n + 1; i <= n + m; i++){for (int j = head[i]; j != -1; j = e[j].next){int v = e[j].to;if (v > n + m) continue;if (e[j].cap == 0){if (v == aa[i - n]) cout << "1";else cout << "0";break;}}}cout << endl;
}int main()
{int t = 1;cin >> t;while (t--){solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！