`
暴风雪
  • 浏览: 387949 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[最小费用流]zoj 3308:Move the Knights

阅读更多

大致题意:

    一个国际象棋棋盘上有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;
}
 
0
0
分享到:
评论

相关推荐

    ZOJ:浙江大学程序在线评测系统.docx

    ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...

    zoj 源码700题

    【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...

    zoj 1002_zoj1002_

    【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...

    zoj 1566 Too Lazy To Move.md

    zoj 1566 Too Lazy To Move.md

    zoj.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar

    标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...

    zoj 1610 Count the Colors.md

    zoj 1610 Count the Colors.md

    zoj 700源代码

    ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...

    zoj1027解题指南

    【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...

    zoj 1255 The Path.md

    zoj 1255 The Path.md

    ZOJ题解集合-截至2835

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...

    pku hdu zoj题目分类

    "图论_网络流入门题.doc"可能包含的是图论的基本概念和网络流算法的学习材料,如最大流、最小割等,这些都是解决网络调度、资源分配等问题的关键。 4. **计算几何**: "POJ 计算几何入门题目.doc"可能介绍了计算...

    ZOJ题目答案源码

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,主要面向计算机科学与信息技术的学生和爱好者,提供了大量的算法题目供参赛者练习和提交代码。"ZOJ题目答案源码"是一个压缩包文件,其中包含了700多道...

    zoj 1810 The Gourmet Club.md

    zoj 1810 The Gourmet Club.md

    zoj 2151 The Highest Profits.md

    zoj 2151 The Highest Profits.md

    zoj 2499 The Happy Worm.md

    zoj 2499 The Happy Worm.md

    zoj 题库 详细解答 解题代码

    zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...

    Problem Arrangement zoj 3777

    Problem Arrangement zoj 3777

    zoj.zip_zoj

    5. **图论**:最小生成树(Prim 或 Kruskal 算法)、最短路径(Floyd-Warshall、Bellman-Ford、Dijkstra 等)、拓扑排序、网络流等问题,这些在解决实际问题如交通网络、电路设计等领域有广泛应用。 6. **字符串...

    ZOJ1003 Crashing Balloon

    【ZOJ1003 Crashing Balloon】这个问题是一个经典的计算机科学竞赛编程题目,主要涉及动态规划(Dynamic Programming, DP)和贪心算法(Greedy Algorithm)的知识点。在这个问题中,参赛者需要编写程序来模拟气球...

Global site tag (gtag.js) - Google Analytics