- 浏览: 376917 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
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 662大致题意: 一个无向图中,每条边都是白边或 ... -
[prim]aizuoj:There is No Alternative
2014-10-20 01:02 845题目地址:http://judge.u-aizu.ac.j ... -
[最大流唯一性判断]hdoj 4888
2014-10-18 16:14 1311题意 给出一个矩阵n行每一行数字的和,m列每列数字的 ... -
[双连通分量+队列优化dijkstra]acdream 1415
2014-10-16 04:03 1095题意: 给出一个n个点,m条边无向图(2 ≤ ... -
[2-sat]hdoj 4751
2014-10-10 21:06 764大致题意 给出一个有向图,问这个图是否能分为两个完全图 ... -
[费用流]hdoj 5045
2014-09-28 00:11 828读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题 ... -
[dfs+bfs]zoj 3811
2014-09-21 09:59 901题意: 在一个无向图中,能否按照一定的顺序访问图 ... -
[二分+最大流]zoj 3691:flower
2013-04-01 21:05 1609大致题意: 在一个三维空间中有n个点,每个点的坐标 ... -
[spfa]hdoj 4460:Friend Chains
2012-11-08 21:15 1593大致题意: 一个无向图n个点,m条边,求任意两个点之 ... -
[二分匹配]zoj 3156:Taxi
2012-10-25 19:28 1067大致题意: 有n个人和m辆车(n<=m)。给出所有 ... -
[Tarjan]uva 4846:Mines
2012-10-19 10:07 1220大致题意: 给出n个地雷,每颗地雷有一个爆炸范围,这 ... -
[2-sat][位运算]zoj 3656:Bit Magic
2012-10-15 09:17 1917大致题意: 给出下面一段代码 很明显这段代码是 ... -
[二分匹配]zoj 3646:Matrix Transformer
2012-10-10 21:15 973大致题意: 给出一个n*n的矩阵,每个矩阵元素的U或者 ... -
[拆点+网络流]2012 acm/icpc成都网络赛 hdoj 4292:Food
2012-09-16 17:15 2214大致题意: 有F种食物和D种饮料,每种食物或饮料只能 ... -
[网络流]2012 acm/icpc成都网络赛hdoj 4288:Control
2012-09-16 17:03 1298大致题意: 给出一个又n个点,m条边组成的无向图。给出两 ... -
[floyd+Tarjan]zoj 3232:It's not Floyd Algorithm
2012-09-09 09:49 1067大致题意: 给出一个有向图的传递闭包矩阵,求出这个图 ... -
[最大流]zoj 3642:Just Another Information Sharing Problem
2012-08-28 13:26 1094大致题意: 有n个人,每个人知道ai个消息,并且会 ... -
[Tarjan变形]zoj 3630:Information
2012-08-15 16:42 1103大致题意: 给出一个有向图,现在要删去一个点使得剩下的图 ... -
[Tarjan强连通分量]hdoj 3836:Equivalent Sets
2012-07-21 09:40 919大致题意: 就是给出一个有向图,求最少加多少条边可以 ... -
[最大流]zoj 3305:Get Sauce
2012-06-19 10:04 930大致题意: 有n种原材料,每种一件。现在给出m个组合 ...
相关推荐
zoj 1566 Too Lazy To Move.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 1610 Count the Colors.md
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
zoj 1255 The Path.md
zoj 1810 The Gourmet Club.md
zoj 2499 The Happy Worm.md
zoj 2151 The Highest Profits.md
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
The reason is that when the director chooses the words from the dictionary and encrypts them, he never changes their order (the words in the dictionary are lexicographically sorted). String a1a2 ... ...
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·