UVA - 10480 Sabotage 输出最小割方案-白红宇的个人博客

UVA - 10480 Sabotage 输出最小割方案

发布日期：2021-05-10 11:28:41 浏览次数：20 分类：精选文章

本文共 3206 字，大约阅读时间需要 10 分钟。

��

��Dinic��

����s�� sink ��t��

����Dinic��s��t��

����

����s��+DFS (DFS + BFS)��s��

����

��

��[��]��

��

#include 
   
    
#include 
    
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl "\n" using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int maxn = 1010; const int maxe = 1010; struct Edge { int u, v; ll w; int next; }; int head[maxn], cnt; bool s_or_t[maxn]; void init() { memset(head, -1, sizeof(head)); s_or_t[u] = false; s = 1; t = 2; } void add(int u, int v, int w) { edge[cnt].u = u; edge[cnt].v = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } bool bfs() { queue
             
               q; q.push(s); deep[s] = 0; now[s] = head[s]; while (q.size()) { int x = q.front(); q.pop(); for (int i = head[x]; i != -1; i = edge[i].next) { int y = edge[i].v; if (edge[i].w > 0 && deep[y] > inf) { if (y == t) return 1; q.push(y); now[y] = head[y]; deep[y] = deep[x] + 1; } } } return 0; } ll dfs(int x, int flow) { if (x == t) return flow; ll ans = 0; for (int i = now[x]; i != -1; i = edge[i].next) { int y = edge[i].v; if (edge[i].w > 0 && (deep[y] == deep[x] + 1)) { ll k = dfs(y, min(flow, edge[i].w)); if (!k) edge[i].w = 0; ans += k; flow -= k; } } return ans; } void dinic() { while (bfs()) { int maxFlows = dfs(s, inf); if (maxFlows == 0) break; } } void output_dfs(int u) { if (s_or_t[u]) return; s_or_t[u] = 1; for (int i = head[u]; i != -1; i = edge[i].next) { if (edge[i].w > 0) { output_dfs(edge[i].v); } } } int main() { IOS; while (cin >> n >> m) { if (!n && !m) break; init(); while (m--) { int u, v, w; cin >> u >> v >> w; add(u, v, w); add(v, u, w); } s = 1; t = 2; dinic(); output_dfs(s); for (int i = 0; i < maxn; i++) { if (s_or_t[i]) { hic rivalry... } } } }

��Dinic��

上一篇：HDU - 2732 Leapin‘ Lizards 拆点最大流+BFS 学好英语QAQ

下一篇：HDU - 4289 Control 拆点最大流，领悟拆点的真谛吧！

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章