1227 方格取数 2 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master
题目描述 Description 给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大
输入描述 Input Description 第一行两个数n,k（1<=n<=50, 0<=k<=10）
接下来n行,每行n个数,分别表示矩阵的每个格子的数
输出描述 Output Description 一个数,为最大和
样例输入 Sample Input 3 1 1 2 3 0 2 1 1 4 2
样例输出 Sample Output 11
数据范围及提示 Data Size & Hint 1<=n<=50, 0<=k<=10
这道题建图有点麻烦，首先要拆点来控制流量，然后的话拆开的两个点要连两条边，一条保证只取一次，另一条保证图的连通性！！ 然后S连到第一个格子的第一个点容量为k，不过k为0的时候要特判一下。。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> using namespace std; const int INF=0x3f3f3f3f; const int maxn=50*50+5; const int maxnode=55; struct Edge { int to,next; int cap,cost; }edge[maxn<<3]; int head[maxn<<1]; int maxedge; inline void addedge(int u,int v,int cap,int cost) { edge[++maxedge]=(Edge){v,head[u],cap,cost}; head[u]=maxedge; edge[++maxedge]=(Edge){u,head[v],0,-cost}; head[v]=maxedge; } int n,k,S,T; inline int id(int i,int j) { return (i-1)*n+j; } inline void init() { scanf("%d%d",&n,&k); maxedge=-1; memset(head,-1,sizeof(head)); S=n*n*2+1,T=S+1; if(k) addedge(S,1,k,0),addedge(n*n<<1,T,k,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { int tmp; scanf("%d",&tmp); int node=id(i,j); addedge(node,node+n*n,1,-tmp); addedge(node,node+n*n,INF,0);//important!! to control path-existed!! if(i+1<=n) addedge(node+n*n,id(i+1,j),INF,0); if(j+1<=n) addedge(node+n*n,id(i,j+1),INF,0); } } bool inque[maxn<<1]; int dis[maxn<<1],add[maxn<<1],pre[maxn<<1]; inline bool spfa() { deque <int> que; memset(dis,0x3f,sizeof(dis)); memset(pre,-1,sizeof(pre)); add[S]=0x3f3f3f3f;inque[S]=true;dis[S]=0;que.push_back(S); while(!que.empty()) { int u=que.front();que.pop_front();inque[u]=false; for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap&&dis[v]>dis[u]+edge[i].cost) { dis[v]=dis[u]+edge[i].cost; add[v]=min(add[u],edge[i].cap); pre[v]=i; if(inque[v]) continue; inque[v]=true; if(que.empty()||dis[v]<dis[que.front()]) if(!que.empty()) que.push_front(v); else que.push_back(v); else que.push_back(v); } } } if(dis[T]>=0x3f3f3f3f) return false; return true; } inline int MCMF() { int flow=0,cost=0; while(spfa()) { flow+=add[T]; cost+=add[T]*dis[T]; for(int i=pre[T];~i;i=pre[edge[i^1].to]) { edge[i].cap-=add[T];edge[i^1].cap+=add[T]; } } return cost; } int main() { freopen("square.in","r",stdin); freopen("square.out","w",stdout); init(); printf("%d",-MCMF()); return 0; }