读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题没有做掉,用了一种错误的构图方式一直t到了最后
其实按照题目中的办法,做m/n次费用流就可以了。
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> using namespace std; const int inf=99999999; const int nMax=1030; const int mMax=30005; struct{ int v, cap, next, re; double cost; }edge[40005]; int nnn,mmm; double ans; int k,edgeHead[nMax]; int que[nMax],pre[nMax]; double dis[nMax]; bool vis[nMax]; void addEdge(int u,int v,int ca,double co){///始点 终点 流量 费用 //cout<<u<<"add"<<v<<" ca="<<ca<<" cost"<<co<<endl; edge[k].v=v; edge[k].cap=ca; edge[k].cost=co; edge[k].next=edgeHead[u]; edge[k].re=k + 1; edgeHead[u]=k ++; edge[k].v=u; edge[k].cap=0; edge[k].cost=-co; edge[k].next=edgeHead[v]; edge[k].re=k - 1; edgeHead[v]=k ++; } bool spfa(){ int i, head = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方 for(i = 0; i <= nnn; i ++){ dis[i] = -1;//////////// vis[i] = false; } dis[0] = 0; que[0] = 0; vis[0] = true; while(head != tail){ int u = que[head]; for(i = edgeHead[u]; i != 0; i = edge[i].next){ int v = edge[i].v; if(edge[i].cap && dis[v] <dis[u] + edge[i].cost){//////// dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]){ vis[v] = true; que[tail ++] = v; if(tail == nMax) tail = 0; } } } vis[u] = false; head++; if(head ==nMax) head = 0; } if(dis[nnn] ==-1) return false;/////////// return true; } //int mark; int n,m; void end(){ int u, p; for(u = nnn; u != 0; u = edge[edge[p].re].v){ p = pre[u]; edge[p].cap -= 1; edge[edge[p].re].cap += 1; ans += edge[p].cost; } } void initspfa(){ k=1; memset(edgeHead,0,sizeof(edgeHead)); memset(vis,0,sizeof(vis)); } double mtx[15][1005]; int main(){ int cnn=0,t,i,j,loc; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ scanf("%lf",&mtx[i][j]); } } loc=1; ans=0; while(loc<=m){ initspfa(); for(i=1;i<=n;i++){ addEdge(0,i,1,0); addEdge(i+n,2*n+1,1,0); } for(i=loc;i<loc+n&&i<=m;i++){ for(j=1;j<=n;j++){ addEdge(j,i-loc+1+n,1,mtx[j][i]); } }nnn=2*n+1; while(spfa())end(); loc+=n; } printf("Case #%d: %.5lf\n",++cnn,ans); } return 0; }
相关推荐
5. **应用领域**:字符串处理、网络流、模拟、游戏理论等。 【压缩包子文件的文件名称列表】:HDOJ题目分类.pdf 这个PDF文档很可能包含了HDOJ平台上所有题目的详细分类列表,每种分类下可能有对应的题目编号、题目...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
5. **IO流**:标准输入输出(System.in和System.out)、文件读写、BufferedReader和PrintWriter等。 6. **面向对象编程**:类、对象、继承、多态、接口等概念的实际应用。 7. **集合框架**:ArrayList、LinkedList...
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
ACM ICPC HDOJ1000
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...
### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...