http://poj.org/problem?id=3422
题目大意：
从左上角走到右下角，中途取数（数>=0），然后该点的数变为0，求走k的总价值和最大值。
——————————————————————————————
最大值？但是我们只会最小费用流啊……
但是数是>=0的啊，所以……
我们拆点，中间连一条容量为1费用为当前值负值的边，再连一条容量为k-1费用0的边。
这样就一定会先走前一条边啦！
然后向下向右连一条容量为k费用0的边。
源点到左上角连一条容量为k-1费用0的边。
右下角到汇点连一条容量为k-1费用0的边。
#include<cstdio> #include<iostream> #include<queue> #include<cstring> #include<algorithm> #include<cctype> using namespace std; typedef long long ll; const int INF=1e9; const int N=50*50*2+10; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct node{ int nxt; int to; int w; int b; }edge[N*N*2]; int head[N],cnt=-1; void add(int u,int v,int w,int b){ cnt++; edge[cnt].to=v; edge[cnt].w=w; edge[cnt].b=b; edge[cnt].nxt=head[u]; head[u]=cnt; return; } int dis[N]; bool vis[N]; inline bool spfa(int s,int t,int n){ deque<int>q; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)dis[i]=INF; dis[t]=0;q.push_back(t);vis[t]=1; while(!q.empty()){ int u=q.front(); q.pop_front();vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; int b=edge[i].b; if(edge[i^1].w&&dis[v]>dis[u]-b){ dis[v]=dis[u]-b; if(!vis[v]){ vis[v]=1; if(!q.empty()&&dis[v]<dis[q.front()]){ q.push_front(v); }else{ q.push_back(v); } } } } } return dis[s]<INF; } int ans=0; int dfs(int u,int flow,int m){ if(u==m){ vis[m]=1; return flow; } int res=0,delta; vis[u]=1; for(int e=head[u];e!=-1;e=edge[e].nxt){ int v=edge[e].to; int b=edge[e].b; if(!vis[v]&&edge[e].w&&dis[u]-b==dis[v]){ delta=dfs(v,min(edge[e].w,flow-res),m); if(delta){ edge[e].w-=delta; edge[e^1].w+=delta; res+=delta; ans+=delta*b; if(res==flow)break; } } } return res; } inline int costflow(int S,int T,int n){ while(spfa(S,T,n)){ do{ memset(vis,0,sizeof(vis)); dfs(S,INF,T); }while(vis[T]); } return ans; } int main(){ memset(head,-1,sizeof(head)); int n=read(); int k=read(); int S=2*n*n+1,T=S+1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int a=read(); int pos=(i-1)*n+j; add(pos,pos+n*n,1,-a); add(pos+n*n,pos,0,a); add(pos,pos+n*n,k-1,0); add(pos+n*n,pos,0,0); pos+=n*n; if(i+1<=n){ int ppos=i*n+j; add(pos,ppos,k,0); add(ppos,pos,0,0); } if(j+1<=n){ int ppos=(i-1)*n+j+1; add(pos,ppos,k,0); add(ppos,pos,0,0); } } } add(S,1,k,0); add(1,S,0,0); add(2*n*n,T,k,0); add(T,2*n*n,0,0); printf("%d ",-costflow(S,T,T)); return 0; }