- 浏览: 387991 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出一个由n个点,m条边组成的有向图,给出切掉每条边的花费。给出f个点和得到这个点的收益值。现在要割掉一些边是的1点和某些城市分开,同时你会得到相应的收益值。求总收益的最大值。
大致思路:
网络流经典构图……
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int nMax=2000; const int mMax=300000; const int inf=1<<30; class node{ public: int u,v,next; int c; int cnm,id; };node edge[mMax]; int ne, head[nMax]; int cur[nMax], ps[nMax], dep[nMax],n,m,ans,cnts,cntt; bool f[nMax],ff[nMax]; void addedge(int u, int v,int c,int id){ // dinic的加边,还是有点不同的。 edge[ne].u = u; edge[ne].v = v; edge[ne].c = c; edge[ne].next = head[u]; edge[ne].cnm=ne+1; edge[ne].id=id; head[u] = ne ++; edge[ne].u = v; edge[ne].v = u; edge[ne].c =0; edge[ne].next = head[v]; edge[ne].cnm=ne-1; edge[ne].id=id; head[v] = ne ++; } int dinic(int s, int t){ // dinic模板:源点为s,汇点为t int tr, res = 0; int i, j, k, f, r, top; while(1){ memset(dep, -1, sizeof(dep)); for(f = dep[ps[0]=s] = 0, r = 1; f != r;) for(i = ps[f ++], j = head[i]; j; j = edge[j].next) if(edge[j].c && dep[k=edge[j].v] == -1){ dep[k] = dep[i] + 1; ps[r ++] = k; if(k == t){ f = r; break; } } if(dep[t] == -1) break; memcpy(cur, head, sizeof(cur)); i = s, top = 0; while(1){ if(i == t){ for(tr = inf, k = 0; k < top; k ++) if(edge[ps[k]].c < tr) tr = edge[ps[f=k]].c; for(k = 0; k < top; k ++){ edge[ps[k]].c -= tr; edge[ps[k]^1].c += tr; } i = edge[ps[top=f]].u; res += tr; // } for(j = cur[i]; cur[i]; j = cur[i] = edge[cur[i]].next) if(edge[j].c && dep[i]+1 == dep[edge[j].v]) break; if(cur[i]){ ps[top ++] = cur[i]; i = edge[cur[i]].v; // }else{ if(top == 0) break; dep[i] = -1; i = edge[ps[-- top]].u; } } } return res; } void dfs1(int v){ // cout<<"v1 "<<v<<endl; f[v] = 1; // cnts++; for(int i = head[v]; i != 0; i = edge[i].next){ int vs=edge[i].v; if(f[vs]==0&&edge[i].c) dfs1(vs); } } void dfs2(int v){ // cout<<"v2 "<<v<<endl; ff[v] = 1; // cntt++; for(int i = head[v]; i != 0; i =edge[i].next){ int vs=edge[i].v; if(ff[vs]==0&&edge[edge[i].cnm].c) dfs2(vs); } } int aaa[mMax]; int main(){ int i,cas,a,b,c,maxflow,fuck,s,t,ans,tim=0; scanf("%d",&cas); while(cas--){ scanf("%d%d%d",&n,&m,&fuck); s=1,t=n+1; ne=2; memset(head,0,sizeof(head)); for(i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); addedge(a,b,c,i); } ans=0; for(i=1;i<=fuck;i++){ scanf("%d%d",&a,&b); addedge(a,t,b,inf); ans+=b; } maxflow=dinic(s,t); ans-=maxflow; printf("Case %d: %d\n",++tim,ans); memset(f,0,sizeof(f)); memset(ff,0,sizeof(ff)); dfs1(s); dfs2(t); int cnt=0; for(i=2;i<ne;i+=2){ if(f[edge[i].u]&&ff[edge[i].v]&&!edge[i].c){ if(edge[i].id==inf)continue; aaa[cnt]=edge[i].id; // cout<<edge[i].id<<"dwadaw"<<endl; cnt++; } } cout<<cnt; for(i=0;i<cnt;i++){ cout<<" "<<aaa[i]; }cout<<endl; } return 0; }
发表评论
-
[kruskal]hdoj 4786
2014-10-29 20:38 699大致题意: 一个无向图中,每条边都是白边或 ... -
[prim]aizuoj:There is No Alternative
2014-10-20 01:02 880题目地址:http://judge.u-aizu.ac.j ... -
[最大流唯一性判断]hdoj 4888
2014-10-18 16:14 1350题意 给出一个矩阵n行每一行数字的和,m列每列数字的 ... -
[双连通分量+队列优化dijkstra]acdream 1415
2014-10-16 04:03 1135题意: 给出一个n个点,m条边无向图(2 ≤ ... -
[2-sat]hdoj 4751
2014-10-10 21:06 809大致题意 给出一个有向图,问这个图是否能分为两个完全图 ... -
[费用流]hdoj 5045
2014-09-28 00:11 866读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题 ... -
[dfs+bfs]zoj 3811
2014-09-21 09:59 971题意: 在一个无向图中,能否按照一定的顺序访问图 ... -
[二分+最大流]zoj 3691:flower
2013-04-01 21:05 1658大致题意: 在一个三维空间中有n个点,每个点的坐标 ... -
[spfa]hdoj 4460:Friend Chains
2012-11-08 21:15 1677大致题意: 一个无向图n个点,m条边,求任意两个点之 ... -
[二分匹配]zoj 3156:Taxi
2012-10-25 19:28 1153大致题意: 有n个人和m辆车(n<=m)。给出所有 ... -
[Tarjan]uva 4846:Mines
2012-10-19 10:07 1295大致题意: 给出n个地雷,每颗地雷有一个爆炸范围,这 ... -
[2-sat][位运算]zoj 3656:Bit Magic
2012-10-15 09:17 2017大致题意: 给出下面一段代码 很明显这段代码是 ... -
[二分匹配]zoj 3646:Matrix Transformer
2012-10-10 21:15 1046大致题意: 给出一个n*n的矩阵,每个矩阵元素的U或者 ... -
[拆点+网络流]2012 acm/icpc成都网络赛 hdoj 4292:Food
2012-09-16 17:15 2309大致题意: 有F种食物和D种饮料,每种食物或饮料只能 ... -
[网络流]2012 acm/icpc成都网络赛hdoj 4288:Control
2012-09-16 17:03 1347大致题意: 给出一个又n个点,m条边组成的无向图。给出两 ... -
[floyd+Tarjan]zoj 3232:It's not Floyd Algorithm
2012-09-09 09:49 1131大致题意: 给出一个有向图的传递闭包矩阵,求出这个图 ... -
[最大流]zoj 3642:Just Another Information Sharing Problem
2012-08-28 13:26 1141大致题意: 有n个人,每个人知道ai个消息,并且会 ... -
[Tarjan变形]zoj 3630:Information
2012-08-15 16:42 1148大致题意: 给出一个有向图,现在要删去一个点使得剩下的图 ... -
[Tarjan强连通分量]hdoj 3836:Equivalent Sets
2012-07-21 09:40 961大致题意: 就是给出一个有向图,求最少加多少条边可以 ... -
[最大流]zoj 3305:Get Sauce
2012-06-19 10:04 970大致题意: 有n种原材料,每种一件。现在给出m个组合 ...
相关推荐
5. **应用领域**:字符串处理、网络流、模拟、游戏理论等。 【压缩包子文件的文件名称列表】:HDOJ题目分类.pdf 这个PDF文档很可能包含了HDOJ平台上所有题目的详细分类列表,每种分类下可能有对应的题目编号、题目...
【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...
HDOJ离线版是该平台的一种特殊形式,它允许用户在没有网络连接的情况下访问和练习HDOJ中的编程题目,对于那些网络环境不稳定或者希望离线学习的程序员来说,这是一个极其宝贵的资源。 离线版通常包含HDOJ平台上的...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...
ACM ICPC HDOJ1002
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
ACM ICPC HDOJ1001
hdoj1001标程
### hdoj1005 Number Sequence 代码分析与解析 #### 一、问题背景与题目概述 在深入了解代码之前,我们先来了解下题目背景。`hdoj1005 Number Sequence` 是杭州电子科技大学在线评测系统(Online Judge,简称OJ)...
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1008
ACM ICPC HDOJ1003
### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md 是工具自动生成 (无聊...
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...
9. 1041.cpp: 可能是一个涉及图论或网络流的问题,需要用到 Ford-Fulkerson 或 Dinic's Algorithm 等算法。 10. 1015.cpp: 最后一个文件可能包含了一个基础的算法问题,比如查找、排序或简单的数学问题,也可能涉及...