注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 2396  

2009-12-30 20:28:51|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这是个典型的有上下界的最大流问题,建模,首先分为m个行点,n个纵点,将源与m个点相连,n个点与汇相连,m与n之间的连线根据限定条件限定大小,然后求最大流,看由源出的边是否满流即可
http://www.ida.liu.se/projects/progcontest/progsm/2003/ 这里有数据,O(∩_∩)O哈哈~,很好用呢
#include<cstdio>
#include<cstring>
const int N=300;
const int inf=~0U>>1;
int up[N][N], low[N][N], flow[N][N]; 
int pv[N], que[N], d[N]; 
void maxflow(int n, int src, int sink) 
{
    int p, q, t, i, j; 
    do{ 
        for (i = 0; i < n; pv[i++] = 0) ; 
        pv[t = src] = src + 1; d[t] = inf; 
        for (p=q=0; p<=q && !pv[sink]; t=que[p++]) 
            for (i=0; i<n; i++) { 
if(!pv[i]&&up[t][i]&&(j=up[t][i]-flow[t][i])>0) 
                    pv[que[q++]=i]=+t+1, d[i]=d[t]<j?d[t]:j; 
                else if (!pv[i]&&up[i][t]&&(j=flow[i][t])>0)
                    pv[que[q++]=i]=-t-1, d[i]=d[t]<j?d[t]:j; 
   } 
   for (i=sink; pv[i] && i!=src; ) {   
if(pv[i]>0)flow[pv[i]-1][i]+=d[sink],i=pv[i]-1; 
            else flow[i][-pv[i]-1]-=d[sink], i=-pv[i]-1; 
  } 
    } while (pv[sink]); 
int limitflow(int n, int src, int sink) 
    int i, j, sk, ks; 
    if (src == sink) return inf; 
  up[n][n+1] = up[n+1][n] = up[n][n] = up[n+1][n+1] = 0;
    for (i = 0; i < n; i++) { 
    up[n][i] = up[i][n] = up[n+1][i] = up[i][n+1] = 0;
        for (j = 0; j < n; j++) { 
            up[i][j] -= low[i][j]; 
   up[n][i] += low[j][i]; 
   up[i][n+1] += low[i][j]; 
  } 
 } 
    sk = up[src][sink]; ks = up[sink][src]; 
    up[src][sink] = up[sink][src] = inf; 
    maxflow(n+2, n, n+1); 
    for (i = 0; i < n; i++) 
        if (flow[n][i] < up[n][i]) return -1; 
    flow[src][sink] = flow[sink][src] = 0; 
    up[src][sink] = sk; up[sink][src] = ks; 
    maxflow(n, src, sink); 
    for (i = 0; i < n; i++) for (j = 0; j < n; j++) { 
        up[i][j] += low[i][j]; flow[i][j] += low[i][j]; 
    for (j = i = 0; i < n; j += flow[src][i++]) ; 
    return j; 
int main(){
    int t,m,n,q,r,v,c;
    char cc;
    scanf("%d\n",&t);
    while(t--){
      bool mark=true;
      int sum2,sum1=sum2=0;
      memset(flow,0,sizeof(flow));
      memset(d,0,sizeof(d));
      memset(que,0,sizeof(que));
      memset(pv,0,sizeof(pv));
      memset(low,0,sizeof(low));
      memset(up,0,sizeof(up));
      scanf("%d%d",&m,&n);
      for(int i=1;i<=m;i++)
        for(int j=m+1;j<=m+n;j++)
          up[i][j]=inf;
      for(int i=0;i<m;i++){
        scanf("%d",&up[0][i+1]);
        sum1+=up[0][i+1];
      }
      for(int i=0;i<n;i++){
        scanf("%d",&up[m+i+1][m+n+1]);    
        sum2+=up[m+i+1][m+n+1];
      }
      scanf("%d",&c);
      for(int k=0;k<c;k++){
        scanf("%d %d %c %d",&q,&r,&cc,&v);
        int i1=1,i2=m,j1=m+1,j2=m+n;
        if(q) i1=i2=q;
        if(r) j1=j2=r+m;
        for(int i=i1;i<=i2;i++)
          for(int j=j1;j<=j2;j++){
            if(cc=='<'&&v-1<up[i][j])
              up[i][j]=v-1;
            if(cc=='>'&&v+1>low[i][j])
              low[i][j]=v+1;
            if(cc=='='){
              up[i][j]=v;
              low[i][j]=v;
            }
          }
      }
      if(sum1==sum2&&mark){
        int ff=limitflow(n+m+2,0,n+m+1);
        if(sum2==ff){
        for(int i=1;i<=m;i++)
            for(int j=m+1;j<=m+n;j++)
              if(flow[i][j]<0)
                mark=false;
          if(mark)
          for(int i=1;i<=m;i++){
            for(int j=m+1;j<=m+n;j++)
              printf("%d ",flow[i][j]);
              printf("\n");
          }else printf("IMPOSSIBLE\n");
          printf("\n");
        }else printf("IMPOSSIBLE\n\n");
      }else printf("IMPOSSIBLE\n\n");
    }
    return 0;
}

  评论这张
 
阅读(1012)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018