题意:懒得打了。LUCKY CAT 里有 http://163.32.78.26/homework/q10330.htm

第一个网络流题目。每个节点都有一个容量值。需要拆点。拆成i - > i + N  边权为容量值

另外注意B个点 连接方式:s - 集合B

D个点 链接方式 集合D + N -> t汇点

其他看处理就好

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == ? b : gcd(b, a % b);}
#define MAXN 250
const int INF = 0x3f3f3f3f ;
int flow[MAXN][MAXN],c[MAXN][MAXN];
int p[MAXN];
int N,M,B,D,src,tag;
void read()
{
memset(c,,sizeof(c));
src = ; tag = * N + ;
for (int i = ; i <= N; i++)
{
int tmp;
scanf("%d",&tmp);
c[i][i + N] = tmp;
}
scanf("%d",&M);
for (int i = ; i <= M; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
c[u + N][v] = w;
}
scanf("%d%d",&B,&D);
for (int i = ; i <= B; i++)
{
int tmp;
scanf("%d",&tmp);
c[][tmp] = INF;
}
for (int i = ; i <= D; i++)
{
int tmp;
scanf("%d",&tmp);
c[tmp + N][tag] = INF;
}
}
int Edmonds_karp(int src,int tag)
{
memset(flow,,sizeof(flow));
int ans = ;
queue<int>q;
while (!q.empty()) q.pop();
int a[MAXN];
while (true)
{
memset(a,,sizeof(a));
a[src] = INF;
q.push(src);
while (!q.empty())
{
int u = q.front(); q.pop();
for (int v = ; v <= tag; v++)
if (!a[v] && c[u][v] > flow[u][v])
{
p[v] = u;
q.push(v);
a[v] = min(a[u],c[u][v] - flow[u][v]);
}
}
if (a[tag] == ) break;
for (int u = tag; u != src; u = p[u])
{
flow[p[u]][u] += a[tag];
flow[u][p[u]] -= a[tag];
}
ans += a[tag];
}
return ans;
}
int main()
{
//freopen("sample.txt","r",stdin);
while (scanf("%d",&N)!=EOF)
{
read();
printf("%d\n",Edmonds_karp(src,tag));
}
return ;
}

最新文章

  1. SQL注入:突破关键字过滤
  2. 洛谷P2014 选课 (树形dp)
  3. Fengshui-[SZU_B40]
  4. jquery对strutrs2 &lt;s:radio&gt;标签的设置和取值
  5. geeksforgeeks@ Equal to product (Binary Search)
  6. MVC5+EF6+BootStrap3.3.5 博客系统之EF(一)
  7. 赵雅智_BroadcastReceiver短信监听
  8. python中从文件中读取数据
  9. 面向服务的体系架构 SOA(二) --- 服务的路由和负载均衡
  10. es索引管理工具-curator
  11. semantic ui框架学习笔记三
  12. activeMq-2 高可用以及集群搭建
  13. vue-cli webpack打包不.map文件,iview 项目打包完,图标路径有问题
  14. linux_添加一个普通用户
  15. kettle 安装mysql 驱动
  16. centos6安装postgresql-(2)
  17. How To Manually Install Oracle Java on Ubuntu
  18. 【JavaScript】particle
  19. [codeforces/gym/101350/L]维护“凸包”
  20. [C#] 类型学习笔记一:CLR中的类型,装箱和拆箱

热门文章

  1. ESP-01S-ESP8266入门教程
  2. python-10多进程
  3. 通过aop添加日志管理
  4. 关于C、内存、栈的一些杂谈
  5. Java密码学综述---密码学基本功能
  6. P1133 教主的花园
  7. miniui IE对省略号即text-overflow:ellipsis显示不一样的问题
  8. 简易版AI英文问答程序解决
  9. 剑指Offer - 九度1507 - 不用加减乘除做加法
  10. Oracle 学习----:查看当前时间与Sqlserver语句不一样了