HDU 3549 — Flow Problem 入门题
admin
2024-04-10 12:54:21
0次

原题：http://acm.hdu.edu.cn/showproblem.php?pid=3549

题意：给定n个点，m条边，以及边上的容量，问1到n的最大流；

#include
#include
#include
#include
#includeusing namespace std;
#define inf 999999999;
const int N = 20;
int cap[N][N], flow[N][N];			//cap表示容量，flow表示当前流量； 
int a[N], p[N];			//a[i]表示从s到i的最小残量，p表示增广路上一节点； 
int n, m;int bfs(int s, int t)
{queueq;memset(flow, 0, sizeof(flow));int ans = 0;while(1){memset(a, 0, sizeof(a));a[s] = inf;q.push(s);while(!q.empty()){int u = q.front();q.pop();for(int v = 1;v<=n;v++){if(!a[v] && cap[u][v]>flow[u][v]){p[v] = u;a[v] = min(a[u], cap[u][v]-flow[u][v]);q.push(v);}}}if(a[t] == 0)break;for(int u = t;u!=s;u = p[u]){flow[p[u]][u]+=a[t];flow[u][p[u]]-=a[t];}ans+=a[t];}return ans;
}int main()
{int cas;int T = 0;scanf("%d", &cas);while(cas--){memset(cap, 0, sizeof(cap));scanf("%d%d", &n, &m);for(int i = 1;i<=m;i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);cap[u][v]+=w;}printf("Case %d: %d\n", ++T, bfs(1, n));}return 0;
}
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：王婆带火的城市，千年前就是顶流了 王婆带火的城市，千年前就是顶流了

下一篇：CentOS 软件包 rpm 管理学习笔记

相关内容

热门资讯

刚收葡萄酒和威士忌，又瞄准黄酒... 在母公司完成对青岛饮料并购后，上市公司青岛啤酒又开始对外“买酒”，这次看中的是黄酒。 5月7日晚间，...
炒腐竹最简单的做法，炒腐竹最简... 炒腐竹最简单的做法教程 特点：食材简单、步骤少、耗时短，适合新手或快速备餐。 一、食材准备（2人份）...
痛心！30岁中国女游客五一期间... 5月7日 #一中国游客为捞相机 命丧87米深海底#的话题 引发关注 据悉，一名30岁的中国女游客在...
靖西崇左自驾游攻略：路线规划难... 启程：与天气预报的博弈（Departure: A Game with the Weather For...
【早安，海棠】5月必吃的几种水... 早安，海棠！‍ 今天是2025年5月7日‍ 星期三（农历四月初十） 海棠天气如何？ 又有哪些健康小知...
摊煎饼，别光顾着调面糊，多加1... 哈喽，大家好，我又来教大家做快手早饭了。 今天教大家做薄薄脆脆的煎饼，搭配着蔬菜，用煎饼把配菜卷起来...
原创 麻... 麻辣肉片是一道经典的川菜，以其麻辣鲜香、肉质嫩滑而深受食客喜爱。这道菜的关键在于肉片的腌制、麻辣调料...
吐峪沟玩水胜地，春天溪涧清凉解... 一、初识吐峪沟 春天的气息悄然弥漫，阳光洒在大地上，为万物披上一层金色的薄纱。周末清晨，我和好友小林...
洪江融媒丨【不去远方 就来洪江... 今年“五一”假期，洪江市以丰富文旅活动与独特景观吸引游客60.96万人次，实现旅游收入10045.9...
贵阳各区市县“五一”旅游成绩单... 2025年“五一”假期，贵阳各区市县文旅活动精彩纷呈。云岩区音乐与美食激活旅游热潮，南明区音乐市集与...
原创 朱... 嘿，亲爱的家人们，五一小长假简直成了明星们的“自由日”！熟悉的主持人朱丹也带着宝贝儿子飞奔到海南，开...
桂林山水甲天下
别再犹豫了！解锁深圳N种玩法，... 喂喂喂！各位在水泥森林里辛勤耕耘的“打工人”们，五一小长假你们是在家“葛优瘫”刷手机，还是勇敢地加入...
周末母亲节，打算陪老妈过节，做... 这个周末就是母亲节了，这次打算回老家陪母亲过节。民以食为天这句话说的没错，不管日子过得如何，总是少不...
酸奶消费警示提示 为帮助广大消费者 正确选购酸奶 玉溪市市场监督管理局 玉溪市消费者协会 发布如下消费提示 一、选购酸...
原创 比... 导语：比芋头便宜、比红薯营养，夏天要使劲吃！一养颜、二补钾、三润肠 大家好，我是傻姐美食，春夏秋冬，...
当孩子爱上烘焙,成绩不好也不是... 作为家长，孩子成长路上的每一个转折点都牵动着我的心。孩子初中成绩不理想，中考后进入技工类学校，本以为...
一高校校庆日支锅炖380斤羊肉...
28款家常菜谱推荐,营养健康又... 在忙碌的生活中，为家人准备一顿营养健康又美味的家常饭菜，是一份无比温馨的心意。接下来，为您推荐 28...
阜新十大特色名菜，一口咬下去全... 要说辽宁哪个城市最有“隐藏剧情”，阜新必须榜上有名。 这地儿早在辽代就是契丹王朝的“中京”，也就是陪...