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