21上海省賽 F-雞哥的限幣令

n個點m條單向邊的圖中，邊上有邊權(quán)，要求選擇一個邊的集合使得每一個點有至少一條連入的邊和一條連出的邊，且這個集合的邊權(quán)和最小。如果不能找到，輸出-1；如果找到了，輸出邊權(quán)和、選擇了幾條邊以及是哪些邊。
數(shù)據(jù)范圍2<=n<=300, 1<=m<=n(n-1)

看數(shù)據(jù)范圍大概可以猜測是一個網(wǎng)絡流，可以通過這道題學習一下上下界網(wǎng)絡流怎么寫。

我們把n個點拆成2n個，每個點由一個入點和一個出點所構(gòu)成，初始的每一條邊都由出點向入點連接，邊的容量為1，費用為w。這樣就可以把題目的要求轉(zhuǎn)化為：每一個入點或者出點都有連邊。

接著我們建立一個源點和一個匯點，源點向每個出點連接一條容量為inf，費用為0，下界為1的邊，每個入點向匯點也連接一條這樣的邊。在這樣的圖上跑一個最小費用可行流就可以完成了。

最后注意的就是輸出的時候邊的編號，因為這個原因半天沒有補出來。

const int N = 1e3 + 10, M = 1e6 + 10, inf = 1e9 + 7; int n, m, s, t; int head[N], now[N], in[N], out[N], dis[N], num = -1; long long ans = 0; bool vis[N];struct edge {int nxt, to, flow, pri; }; edge e[M];void addEdge(int x, int y, int z, int w) {e[++ num].nxt = head[x];head[x] = num;e[num].to = y;e[num].flow = z;e[num].pri = w; }bool spfa() {for (int i = 1; i <= 2 * n + 4; i ++)dis[i] = inf;dis[s] = 0;queue <int> q;q.push(s);while (!q.empty()){int x = q.front(); q.pop();for (int i = head[x]; i != -1; i = e[i].nxt){int to = e[i].to;if(dis[to] > dis[x] + e[i].pri && e[i].flow > 0){dis[to] = dis[x] + e[i].pri;q.push(to);}}}if (dis[t] == inf) return false;return true; }int dfs(int x, int flow) {if (vis[x])return 0;vis[x] = 1;if (x == t)return flow;for (int i = now[x]; i != -1; i = e[i].nxt){now[x] = i;int to = e[i].to;if (dis[to] == dis[x] + e[i].pri && e[i].flow > 0){int val = dfs(to, min(flow, e[i].flow));if (val > 0){e[i].flow -= val;e[i ^ 1].flow += val;ans += val * e[i].pri;return val;}}}return 0; }void dinic(int x, int y) {s = x; t = y;while (spfa()){for (int i = 1; i <= 2 * n + 4; i ++){vis[i] = 0;now[i] = head[i];}int val = 0;while (val = dfs(s, inf)){if (val == 0)break;}} }int main() {//freopen("in.txt", "r", stdin);memset (head, -1, sizeof (head));n = read(); m = read();for (int i = 1; i <= m; i ++){int u, v, w;u = read(); v = read(); w = read();out[u] = in[v] = 1;addEdge (u, v + n, 1, w);addEdge (v + n, u, 0, -w);}bool flag = true;for (int i = 1; i <= n; i ++)if (!out[i] || !in[i])flag = false;if (!flag){cout << -1;return 0;}memset (in, 0, sizeof (in));memset (out, 0, sizeof (out));for (int i = 1; i <= n; i ++){out[2 * n + 1] ++;in[i] ++;addEdge(2 * n + 1, i, inf, 0);addEdge(i, 2 * n + 1, 0, 0);}for (int i = n + 1; i <= n * 2; i ++){out[i] ++;in[2 * n + 2] ++;addEdge(i, 2 * n + 2, inf, 0);addEdge(2 * n + 2, i, 0, 0);}addEdge(2 * n + 2, 2 * n + 1, inf, 0);addEdge(2 * n + 1, 2 * n + 2, 0, 0);for (int i = 1; i <= 2 * n + 2; i ++){if (in[i] > out[i]){addEdge(2 * n + 3, i, in[i] - out[i], 0);addEdge(i, 2 * n + 3, 0, 0);}if (in[i] < out[i]){addEdge(i, 2 * n + 4, out[i] - in[i], 0);addEdge(2 * n + 4, i, 0, 0);}}dinic(2 * n + 3, 2 * n + 4);int tot = 0;queue <int> q;for (int i = 0; i < m; i ++)if (!e[i << 1].flow){q.push(i + 1);++ tot;}cout << ans << endl;printf ("%d ", tot);while (!q.empty()){int now = q.front();q.pop();printf ("%d", now);if (!q.empty())printf (" ");}return 0; } 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的21上海省赛 F-鸡哥的限币令的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。