网络流基础题目,Edmonds_Karp可解。

 /* 3549 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
using namespace std; #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 pb push_back
#define mp make_pair
#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 const int maxn = ;
int F[maxn][maxn];
int P[maxn], a[maxn];
int n, m, ans;
int s, t; bool bfs() {
int u, v;
queue<int> Q; memset(a, , sizeof(a));
a[s] = INT_MAX;
Q.push(s);
P[s] = s; while (!Q.empty()) {
u = Q.front();
Q.pop();
for (v=; v<=n; ++v) {
if (!a[v] && F[u][v]) {
P[v] = u;
Q.push(v);
a[v] = min(a[u], F[u][v]);
}
}
} return a[t] == ;
} void Edmonds_Karp() {
int u, v; s = ;
t = n;
ans = ; while (true) {
if (bfs())
break;
for (u=t; u!=s; u=P[u]) {
F[u][P[u]] += a[t];
F[P[u]][u] -= a[t];
}
ans += a[t];
}
} int main() {
int i, j, k;
int t, tt; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif scanf("%d", &tt);
for (t=; t<=tt; ++t) {
scanf("%d %d", &n, &m);
memset(F, , sizeof(F));
while (m--) {
scanf("%d %d %d", &i, &j, &k);
F[i][j] += k;
}
Edmonds_Karp();
printf("Case %d: %d\n", t, ans);
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}

最新文章

  1. 移动前端不得不了解的html5 head 头标签
  2. mplayer-1.3.0-2016-09-01.7z
  3. Java 网络编程学习总结
  4. HTTP 请求报文 响应报文
  5. js自定义延迟执行函数
  6. 完整的Ajax实例
  7. php中使用随机数
  8. Lua 数据类型和 Redis 数据类型之间转换
  9. sublime text3 配置使用
  10. C#程序打包安装部署
  11. 斑马ZPL指令加入如换行、回车等控制符的方法
  12. api-gateway实践(16)【租户模块:修改api定义】通过mq通知【开发者模块:更新开发者集市】
  13. AbstractRoutingDataSource实现动态数据源切换 专题
  14. docker企业实战视频教程
  15. 开发环境之git:团队协作git工作流与常用命令
  16. Oracle DBLINK 简单使用
  17. SQLServer和MySql的区别总结
  18. python 遇到的一些坑
  19. java将数据从List转换Map
  20. ios 确定文字所占矩形框大小

热门文章

  1. 微信45028错误,微信has no masssend quota hint错误
  2. Andriod中WebView加载登录界面获取Cookie信息并同步保存,使第二次不用登录也可查看个人信息。
  3. BufferedWriter和BufferedReader使用方法
  4. file的name值
  5. ASP.NET MVC——Controller的激活
  6. Delphi Excel
  7. Lucene的Query类介绍
  8. Codeforces 551D GukiZ and Binary Operations(矩阵快速幂)
  9. CSS3圆角(border-radius)
  10. LICAppInfo