首页 > 代码库 > Jump
Jump
hdu4862：http://acm.hdu.edu.cn/showproblem.php?pid=4862
题意：给你n*m的方格，每个方格中有一个数(0---9),然后你每次可以选择一个点开始，这个点是之前没有访问过的，然后你可以向右边的的方格跳，也可以向下面的方格跳。跳的过程中，你会丢失(x2-x1)+(y2-y1)-1一些能量。如果下一个方格和现在的方格的数字相同，那么你可以得到一些能量。每次一开始，你就可以随便跳。但是你最多只能选择k次开始。为你得到的最多能量，并且每个格子只访问一次。
题解：剖析一下，就知道，这一题是求最小k条路径覆盖(如果把边权取负的话)。接下是如果求解这个模型。建图方式如下。
把原图中点分成两部分X(n*m个)，Y(n*m个)，原图中的边(u,v,w),改成(u,v+n*m,-w);然后源点与X部分的每一点建一条边(st,x,0),然后st与p之间建一条边(st,p,0),容量为k，然后p与Y的每一点建一条边，然后Y与汇点建立一条边，这些变的容量都是1，费用都是0.然后跑最小费用最大流，如果满流则能跑完每个格子一次。否则不能。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define inf 100000000 7 using namespace std; 8 const int E=1000000; 9 const int N=10002; 10 struct{ 11 int v, cap, cost, next; // re记录逆边的下标。 12 }edge[E]; 13 int n, m, ans,flow; 14 int k, cnt,head[N]; 15 int que[N], pre[N], dis[N]; 16 bool vis[N]; 17 char mp[12][12]; 18 void init(){//初始化 19 cnt=ans=0,flow=0; 20 memset(head,-1,sizeof(head)); 21 } 22 void addEdge(int u, int v, int ca, int co){ 23 edge[cnt].v = v; 24 edge[cnt].cap = ca; 25 edge[cnt].cost = co; 26 edge[cnt].next = head[u]; 27 head[u] = cnt ++; 28 edge[cnt].v = u; 29 edge[cnt].cap = 0; 30 edge[cnt].cost = -co; 31 edge[cnt].next = head[v]; 32 head[v] = cnt++; 33 } 34 bool spfa(){ // 源点为0，汇点为n。 35 int i; 36 for(i = 0; i <= 2*m*n+2; i ++){ 37 dis[i] = inf; 38 vis[i] = false; 39 } 40 queue<int>Q; 41 Q.push(2*n*m+1); 42 dis[2*n*m+1]=0; 43 vis[2*n*m+1] = true; 44 while(!Q.empty()){ // 这里最好用队列，有广搜的意思，堆栈像深搜。 45 int u = Q.front(); 46 Q.pop(); 47 for(i = head[u]; i != -1; i = edge[i].next){ 48 int v = edge[i].v; 49 if(edge[i].cap && dis[v] > dis[u] + edge[i].cost){ 50 dis[v] = dis[u] + edge[i].cost; 51 pre[v] = i; 52 if(!vis[v]){ 53 vis[v] = true; 54 Q.push(v); 55 } 56 } 57 } 58 vis[u] = false; 59 } 60 if(dis[2*n*m+2] == inf) return false; 61 return true; 62 } 63 void end(){ 64 int u, p, sum = inf; 65 for(u = 2*n*m+2; u !=2*n*m+1; u = edge[p^1].v){//0是超级源点 66 p = pre[u]; 67 sum = min(sum, edge[p].cap); 68 } 69 for(u = 2*n*m+2; u != 2*n*m+1; u = edge[p^1].v){ 70 p = pre[u]; 71 edge[p].cap -= sum; 72 edge[p^1].cap += sum; 73 ans += sum * edge[p].cost; // cost记录的为单位流量费用，必须得乘以流量。 74 } 75 flow+=sum; 76 } 77 78 void input(){ 79 memset(mp,0,sizeof(mp)); 80 for(int i=1;i<=n;i++){ 81 for(int j=1;j<=m;j++) 82 cin>>mp[i][j]; 83 } 84 } 85 void build(){ 86 for(int i=1;i<=n;i++) 87 for(int j=1;j<=m;j++){ 88 for(int k=j+1;k<=m;k++){ 89 if(mp[i][j]==mp[i][k]) 90 addEdge((i-1)*m+j,(i-1)*m+k+n*m,1,k-j-1-(mp[i][j]-‘0‘)); 91 else 92 addEdge((i-1)*m+j,(i-1)*m+k+n*m,1,k-j-1); 93 94 } 95 for(int k=i+1;k<=n;k++){ 96 if(mp[i][j]==mp[k][j]) 97 addEdge((i-1)*m+j,(k-1)*m+j+n*m,1,k-i-1-(mp[i][j]-‘0‘)); 98 else 99 addEdge((i-1)*m+j,(k-1)*m+j+n*m,1,k-i-1);100 }101 102 }103 for(int i=1;i<=n*m;i++){104 addEdge(2*m*n+1,i,1,0);105 addEdge(0,i+n*m,1,0);106 addEdge(i+n*m,2*n*m+2,1,0);107 }108 addEdge(2*n*m+1,0,k,0);109 }110 int cas;111 int main(){112 int tt=1;113 scanf("%d",&cas);114 while(cas--){115 scanf("%d%d%d",&n,&m,&k);116 input();117 init();118 build();119 while(spfa())end();120 if(flow==n*m){121 printf("Case %d : %d\n",tt++,-ans);122 }123 else{124 printf("Case %d : -1\n",tt++);125 }126 }127 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。