【HDU 2014 Multi-University Training Contest 1 1002】/【HDU 4862】Jump-白红宇

【HDU 2014 Multi-University Training Contest 1 1002】/【HDU 4862】Jump

阅读量：5311 次

发布时间：2019-06-14

本文共 2225 字，大约阅读时间需要 7 分钟。

多校训练就这么华丽丽的到了，于是乎各种华丽丽的被虐也開始了。

这是多校的1002; 最小费用最大流。

题目大意：

有n*m个方格，每一个方格都一个的十进制一位的数。你能够操作K次。

对于每一次操作，你能够选择一个出发点向下或向右Jump。跳的花费是|x1-x2|+|y1-y2|-1的能量。假设你跳的这两个位置上数字同样，那么你就会获得数字表示的能量值。

对于每一次操作，你能够这样跳随意次，可是每一个位置仅仅能经过一次在这K次操作中。

初始能量值是0，当操作完毕后，假设n*m个方格没有都经过过，输出“-1”，否则输出能够得到的最大能量值。

解题思路：

建立一个流量网络，一个二部图。X部分向Y部分链接的情况表示能够从一个点跳到还有一个点，超级源点和超级汇点分别同X部分的点和Y部分的点链接。在X部分中多加一个点它与源点的流量是K费用是0，与Y部分全部点链接流量是1费用是0。这表示操作K次。

以下是代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #define clear(A, X, SIZE) memset(A, X, sizeof(A[0]) * (SIZE))#define clearall(A, X) memset(A, X, sizeof(A))#define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE))#define memcopy1all(A, X) memcpy(A , X ,sizeof(X))#define max( x, y ) ( ((x) > (y)) ? (x) : (y) )#define min( x, y ) ( ((x) < (y)) ? (x) : (y) )using namespace std;struct node{ int u,v,c,f,next;} edge[21000];char s[12][15];const int inf=1<<30;int head[210],cnt,dis[210],pre[210],n,m,cost,flow;bool vis[210];bool spfa(){ int i,u; clearall(pre,-1); clearall(dis,0x3f3f3f); clearall(vis,false); queue 
                
                 q; dis[n*m*2]=0; vis[n*m*2]=true; q.push(n*m*2); while(!q.empty()) { u=q.front(); q.pop(); i=head[u]; vis[u]=false; while(i!=-1) { if(edge[i].f>0&&dis[edge[i].v]>dis[u]+edge[i].c) { dis[edge[i].v]=dis[u]+edge[i].c; pre[edge[i].v]=i; if(!vis[edge[i].v]) { vis[edge[i].v]=true; q.push(edge[i].v); } } i=edge[i].next; } } if(pre[2*n*m+1]==-1)return false; else return true;}void does(){ cost=0; flow=0; while(spfa()) { int max1=inf; int p=pre[2*n*m+1]; while(p!=-1) { max1=min(max1,edge[p].f); p=pre[edge[p].u]; } p=pre[2*n*m+1]; while(p!=-1) { edge[p].f-=max1; edge[p^1].f+=max1; cost+=max1*edge[p].c; p=pre[edge[p].u]; } flow+=max1; }}void addedge(int u,int v,int f,int c){ edge[cnt].u=u; edge[cnt].v=v; edge[cnt].f=f; edge[cnt].c=c; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].u=v; edge[cnt].v=u; edge[cnt].f=0; edge[cnt].c=-c; edge[cnt].next=head[v]; head[v]=cnt++;}int main(){ int T,k,case1=1,u,v,f,c; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); for(int i=0; i

转载于:https://www.cnblogs.com/zfyouxi/p/3871721.html

你可能感兴趣的文章

[Flex] flex手机项目如何限制横竖屏？只允许横屏？