- 浏览: 388855 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
一个国际象棋棋盘上有n个马分布在不同的黑色格子上,这些棋子共有三种,“金马”移动的能量损耗是P(row1,col1) x P(row2,col2),“银马”是P(row1,col1) + P(row2,col2),铜马是max(P(row1,col1) , P(row2,col2))。现在允许n个棋子中有k个棋子移动一步,求移动的马数量最多时最少能量消耗是多少。
大致思路:
一开时没看到所有的马都在黑格子上,被卡,想到了就是裸构图费用流~~
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int inf=99999999; const int nMax=3000; const int mMax=20000; struct{ int u,v, cap, cost, next, re; }edge[mMax]; int ans,maxf; int k,edgeHead[nMax]; int que[nMax],pre[nMax],dis[nMax]; bool vis[nMax],flag; int K; void addEdge(int u,int v,int ca,int co){////始点 终点 流量 花费 // cout<<u<<" add "<<v<<" val= "<<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 s,int t,int n){ //始点,终点,总点数 int i, head = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方 for(i = 0; i <= n; i ++){ dis[i] = inf;//////////// vis[i] = false; } dis[s] = 0; que[0] = s; vis[s] = 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[t] ==inf) return false;/////////// return true; } void end(int s,int t){ int u, p; for(u = t;u!=s;u=edge[edge[p].re].v){ p = pre[u]; edge[p].cap-=1; edge[edge[p].re].cap+=1; ans+=edge[p].cost; } maxf+=1; //总流量 } int dx[4]={1,-1,2,-2}; int dy[4]={2,-2,1,-1}; int map[20][20]; int r,c,n; int abs(int a){if(a>0)return a;return -a;} void build(int m,int a,int b){ int x,y,i,j,val; for(i=0;i<4;i++){ for(j=0;j<4;j++){ if(abs(dy[i])==abs(dx[j])){ continue; } y=a+dy[i]; x=b+dx[j]; if(y>0&&y<=r&&x>0&&x<=c){ if(m==1){ val=map[y][x]*map[a][b]; } if(m==2){ val=map[y][x]+map[a][b]; } if(m==3){ val=max(map[y][x],map[a][b]); } int s=(a-1)*c+b; int t=(y-1)*c+x; // cout<<s<<" "<<t<<endl; // cout<<s<<" "<<t-r*c<<" "<<val<<endl; addEdge(s,t,1,val); } } } } int main(){ int i,j,a,b,x,y,m,kkk,s,t; while(cin>>r>>c>>n>>kkk){ for(i=1;i<=r;i++){ for(j=1;j<=c;j++){ scanf("%d",&map[i][j]); } } ans=0; maxf=0; k=1; memset(edgeHead,0,sizeof(edgeHead)); addEdge(0,15*15*4,kkk,0); for(i=0;i<n;i++){ cin>>m>>a>>b; build(m,a,b); } for(i=1;i<=r;i++){ for(j=1;j<=c;j++){ a=(i-1)*c+j; // cout<<"fuck"<<i<<" "<<j<<"="<<a<<endl; if((i+j)%2==0) { addEdge(15*15*4,a,1,0); } else{ addEdge(a,15*15*4+1,1,0); } } } s=0; t=15*15*4+1; while(spfa(s,t,15*15*5))end(s,t); if(!maxf){ cout<<-1<<endl; } else{ cout<<ans<<endl; } } return 0; }
发表评论
-
[kruskal]hdoj 4786
2014-10-29 20:38 703大致题意: 一个无向图中,每条边都是白边或 ... -
[prim]aizuoj:There is No Alternative
2014-10-20 01:02 883题目地址:http://judge.u-aizu.ac.j ... -
[最大流唯一性判断]hdoj 4888
2014-10-18 16:14 1358题意 给出一个矩阵n行每一行数字的和,m列每列数字的 ... -
[双连通分量+队列优化dijkstra]acdream 1415
2014-10-16 04:03 1137题意: 给出一个n个点,m条边无向图(2 ≤ ... -
[2-sat]hdoj 4751
2014-10-10 21:06 815大致题意 给出一个有向图,问这个图是否能分为两个完全图 ... -
[费用流]hdoj 5045
2014-09-28 00:11 868读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题 ... -
[dfs+bfs]zoj 3811
2014-09-21 09:59 978题意: 在一个无向图中,能否按照一定的顺序访问图 ... -
[二分+最大流]zoj 3691:flower
2013-04-01 21:05 1668大致题意: 在一个三维空间中有n个点,每个点的坐标 ... -
[spfa]hdoj 4460:Friend Chains
2012-11-08 21:15 1684大致题意: 一个无向图n个点,m条边,求任意两个点之 ... -
[二分匹配]zoj 3156:Taxi
2012-10-25 19:28 1163大致题意: 有n个人和m辆车(n<=m)。给出所有 ... -
[Tarjan]uva 4846:Mines
2012-10-19 10:07 1303大致题意: 给出n个地雷,每颗地雷有一个爆炸范围,这 ... -
[2-sat][位运算]zoj 3656:Bit Magic
2012-10-15 09:17 2030大致题意: 给出下面一段代码 很明显这段代码是 ... -
[二分匹配]zoj 3646:Matrix Transformer
2012-10-10 21:15 1052大致题意: 给出一个n*n的矩阵,每个矩阵元素的U或者 ... -
[拆点+网络流]2012 acm/icpc成都网络赛 hdoj 4292:Food
2012-09-16 17:15 2321大致题意: 有F种食物和D种饮料,每种食物或饮料只能 ... -
[网络流]2012 acm/icpc成都网络赛hdoj 4288:Control
2012-09-16 17:03 1353大致题意: 给出一个又n个点,m条边组成的无向图。给出两 ... -
[floyd+Tarjan]zoj 3232:It's not Floyd Algorithm
2012-09-09 09:49 1138大致题意: 给出一个有向图的传递闭包矩阵,求出这个图 ... -
[最大流]zoj 3642:Just Another Information Sharing Problem
2012-08-28 13:26 1143大致题意: 有n个人,每个人知道ai个消息,并且会 ... -
[Tarjan变形]zoj 3630:Information
2012-08-15 16:42 1155大致题意: 给出一个有向图,现在要删去一个点使得剩下的图 ... -
[Tarjan强连通分量]hdoj 3836:Equivalent Sets
2012-07-21 09:40 963大致题意: 就是给出一个有向图,求最少加多少条边可以 ... -
[最大流]zoj 3305:Get Sauce
2012-06-19 10:04 971大致题意: 有n种原材料,每种一件。现在给出m个组合 ...
相关推荐
ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...
【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...
【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...
zoj 1566 Too Lazy To Move.md
标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...
zoj 1610 Count the Colors.md
ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...
【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...
zoj 1255 The Path.md
ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...
"图论_网络流入门题.doc"可能包含的是图论的基本概念和网络流算法的学习材料,如最大流、最小割等,这些都是解决网络调度、资源分配等问题的关键。 4. **计算几何**: "POJ 计算几何入门题目.doc"可能介绍了计算...
ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,主要面向计算机科学与信息技术的学生和爱好者,提供了大量的算法题目供参赛者练习和提交代码。"ZOJ题目答案源码"是一个压缩包文件,其中包含了700多道...
zoj 1810 The Gourmet Club.md
zoj 2499 The Happy Worm.md
zoj 2151 The Highest Profits.md
zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...
Problem Arrangement zoj 3777
5. **图论**:最小生成树(Prim 或 Kruskal 算法)、最短路径(Floyd-Warshall、Bellman-Ford、Dijkstra 等)、拓扑排序、网络流等问题,这些在解决实际问题如交通网络、电路设计等领域有广泛应用。 6. **字符串...
【ZOJ1003 Crashing Balloon】这个问题是一个经典的计算机科学竞赛编程题目,主要涉及动态规划(Dynamic Programming, DP)和贪心算法(Greedy Algorithm)的知识点。在这个问题中,参赛者需要编写程序来模拟气球...