首页 > 代码库 > bzoj1927
bzoj1927
题意：给定一个图，还有一些有向边，每条边有一个权值w。对于每一个点，可以从其他任意一个点转移到这个点，时间为t。求从图外的一个点（即第一次一定是通过转移方式），遍历图中每个点一次最少需要的时间。。
思路：
对于图中的每个点，需要满足的要求是进入一次，出去一次（即遍历一边）
所以我们很容易想到拆点，把每个点拆成两个点。建图如下：
<S, i, 1, 0>对应每个点进入一次
<i+n, T, 1, 0>对应每个点出去一次
<i, j + n, 1, wij>，如果ij有边对应i走到j
<S, i, 1, t[i]>对应可以从其他点转移到这个点
这样跑一遍最小费用流就是答案。
code：
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define M0(a) memset(a, 0, sizeof(a)) 4 #define Inf 0x3fffffff 5 const int maxn = 2010; 6 const int maxm = 200010; 7 struct edge{ 8 int v, f, c, next; 9 edge(){}10 edge(int _v, int _f, int _c, int _next):v(_v), f(_f), c(_c), next(_next){}11 };12 struct Costflow{13 int last[maxn], pre[maxn], dis[maxn], vis[maxn];14 int tot, S, T;15 edge e[maxm];16 void add(int u, int v, int f, int c){17 e[tot] = edge(v, f, c, last[u]); last[u] = tot++;18 e[tot] = edge(u, 0, -c, last[v]); last[v] = tot++; 19 }20 void init(int S, int T){21 this->S = S, this->T = T;22 M0(e);23 memset(last, -1, sizeof(last));24 tot = 0; 25 }26 int spfa(){27 for (int i = 0; i <= T; ++i)28 dis[i] = Inf;29 memset(vis, 0, sizeof(vis));30 memset(pre, -1, sizeof(pre));31 dis[S] = 0;32 queue<int> q;33 q.push(S) , vis[S] = 1;34 int p, u, v;35 while (!q.empty()){36 p = last[u = q.front()];37 for ( ; p > -1; p = e[p].next){38 v = e[p].v;39 if (dis[u] + e[p].c < dis[v] && e[p].f > 0){40 dis[v] = dis[u] + e[p].c;41 pre[v] = p;42 if (!vis[v]) vis[v] = 1, q.push(v);43 } 44 }45 vis[u] = 0;46 q.pop(); 47 }48 return dis[T] < Inf; 49 }50 int costflow(){51 int cost = 0, flow = 0;52 while (spfa()){53 int f = Inf;54 for (int p = pre[T]; p != -1; p = pre[e[p^1].v])55 f = min(f, e[p].f);56 flow += f;57 cost += f * dis[T];58 for (int p = pre[T]; p != -1; p = pre[e[p^1].v])59 e[p].f -= f, e[p^1].f += f; 60 }61 return cost;62 }63 /***********/ 64 } F;65 int n, m;66 int t[maxn];67 68 void solve(){69 // printf("%d %d\n", n, m);70 for (int i = 1; i <= n; ++i)71 scanf("%d", t+i);72 int S = 0, T = 2 * n + 1;73 F.init(S, T);74 for (int i = 1; i <= n; ++i)75 F.add(S, i + n, 1, t[i]), F.add(i+n, T, 1, 0), F.add(S, i, 1, 0);76 int u, v, w;77 for (int i = 1; i <= m; ++i){78 scanf("%d%d%d", &u, &v, &w);79 if (u > v) swap(u, v);80 F.add(u, v+n, 1, w);81 }82 int ans = F.costflow();83 cout << ans << endl;84 }85 86 int main(){87 while (scanf("%d%d", &n, &m) != EOF){88 solve();89 } 90 }
bzoj1927
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。