[最小费用流]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;
}