2014湘潭全国邀请赛I题 Intervals /POJ 3680 / 在限制次数下取有权区间使权最大/小问题(费用流)

时间:2022-01-31 16:03:37

先说POJ3680:给n个有权(权<10w)开区间(n<200),(区间最多数到10w)保证数轴上所有数最多被覆盖k次的情况下要求总权最大,输出最大权。

  思路:       限制的处理:s-->开始流量为k,要求总权最大,即费用最大,所以费用取负,最小费用最大流即可。对于输入区间[a,b]:w,添加边:a-->b,流量为1,费用为-w。

                  对于点i,i+1,添加边,费用为0,流量无穷。显然这种处理,限制了区间最多取k次,(流量控制),跑最大流能走添加的边尽量走,且越大越好(负数刚刚是最小费用),满足题意。但是TLE,因为w到10W,边10W,必然超时    ,所以点要处理,  所有点“压缩”,向前推进,只要存在的点,前一个向后一个连边即可,详见代码。


再看湘潭的这题: 问题相反:给n个有权(权<10w)开区间(n<2000),(区间最多数到10的9次),保证区间【1-,m】最少被覆盖k次的情况下要求总权最小,输出最小权。

 思路:(感激zz1215的建图提示)    限制的处理:显然在出口处流量必需达到k才算有解。对于输入区间[a,b]:w,添加边:a-->b,流量为1,费用为w,但是这样处理,点都是离散的,根本没有体现连续性,

不可能像上题那样建图(否则费用为0),所以:这样:点I向它前一个点连边,费用为0,流量为无穷,这样巧妙的解决了离散点问题。跑最小费用即可。显然,之前要处理点。

2014湘潭全国邀请赛I题 Intervals /POJ 3680 / 在限制次数下取有权区间使权最大/小问题(费用流)

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int t=100000;
int n,k;
int e[300001][4];int head[100101];int nume=0;
void inline adde(int from,int to,int w,int c)
{
    e[nume][0]=to;e[nume][1]=head[from];head[from]=nume;
    e[nume][2]=w;e[nume++][3]=c;
    e[nume][0]=from;e[nume][1]=head[to];head[to]=nume;
    e[nume][2]=-w;e[nume++][3]=0;
}
int inq[111005];int d[110000];              //spfa
bool spfa(int & sumcost)               //每次求费用
{
    int pre[110005];
    int minf=inf;
    int prv[110005];
    for(int i=0;i<=t+1;i++)
      {
          inq[i]=0;d[i]=inf;
      }
    pre[0]=-1 ; prv[0]=-1;       //路径中,分别记录到点i的边,和i之前的点。(这题如果用矩阵建图要方便)
    queue<int>q;
    q.push(0);inq[0]=1;d[0]=0;
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        inq[cur]=0;
         for(int i=head[cur];i!=-1;i=e[i][1])
         {
             int v=e[i][0];
             if(e[i][3]>0&&e[i][2]+d[cur]<d[v])
             {
                 d[v]=e[i][2]+d[cur];
                 prv[v]=cur;               //记录增广路
                 pre[v]=i;
                 if(!inq[v])
                 {
                     q.push(v);
                     inq[v]=1;
                 }
             }
         }
    }
     if(d[t+1]==inf)return 0;       //无法增广
     int cur=t+1;                   //目的点
     while(cur!=0)              //取路径上最小残流量边作为流量增广
    {
        minf=e[pre[cur]][3]<minf?e[pre[cur]][3]:minf;
        cur=prv[cur];
    }
    cur=t+1;
    while(cur!=0)                 //增广,改流量
    {
         e[pre[cur]][3]-=minf;
         e[pre[cur]^1][3]+=minf;
         cur=prv[cur];
    }
   sumcost+=d[t+1]*minf;         //费用为单位费用(该路径下每条边单位流量之和)*流量
   return 1;
}
void mincost(int & sumcost)
{
    while(spfa(sumcost)) ;     //无法增广为止
    return ;
}
int hash[100011];
void clear()
{
    nume=0;
    for(int i=0;i<=t+1;i++)
      {
          hash[i]=head[i]=-1;
      }
}
struct qujian
{
    int a,b,w;
};
int main()
{
   int T;
    scanf("%d",&T);
   for(int ii=1;ii<=T;ii++)
   {
       clear();
       cin>>n>>k;
       int a,b,w;
        vector<qujian>qq(n);
        vector<int>v;
       for(int i=0;i<n;i++)
       {
           scanf("%d%d%d",&a,&b,&w);
            hash[a]=hash[b]=1;            
            qq[i].a=a;qq[i].b=b;qq[i].w=w;
            adde(a,b,-w,1);
       }
       for(int i=0;i<100010;i++)     //处理“存在”的点
         if(hash[i]==1)
         {
             v.push_back(i);
         }
       for(int i=0;i<v.size()-1;i++)   //“存在”的点连边
       {
           adde(v[i],v[i+1],0,k);
       }
       adde(v[v.size()-1],t,0,k);              //超级源汇点的边
       adde(0,v[0],0,k);adde(t,t+1,0,k);
         int sumcost=0;
       mincost(sumcost);
       cout<<-sumcost<<endl;              //相反数
   }
   return 0;
}


湘潭:

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,k,m;
int countv=0;
int f[4009];
void getf(int x)     // 把点1到10的9次(最多4000个点),压缩到4000以内,一一对应,以便建图。
{
    if(x>m){f[countv]=x;return ;}    //大于m的数没用,相当于m。
    countv++;
    f[countv]=x;
}
int getv(int x)         //获取对应点
{
    if(x>=m){return countv;}
    for(int i=1;i<=countv;i++)
    {
        if(f[i]==x)return i;
    }
}
int e[20001][4];int head[4005];int nume=0;
void inline adde(int from,int to,int w,int c)
{
    e[nume][0]=to;e[nume][1]=head[from];head[from]=nume;
    e[nume][2]=w;e[nume++][3]=c;
    e[nume][0]=from;e[nume][1]=head[to];head[to]=nume;
    e[nume][2]=-w;e[nume++][3]=0;
}
int inq[4005];int d[4005];              //spfa
bool spfa(int & sumcost,int &sumflow)               //每次求费用
{
    int pre[4005];
    int minf=inf;
    int prv[4005];
    for(int i=0;i<=countv+4;i++)
      {
          inq[i]=0; d[i]=inf;
      }
    pre[0]=-1 ; prv[0]=-1;       //路径中,分别记录到点i的边,和i之前的点。(这题如果用矩阵建图要方便)
    queue<int>q;
    q.push(0);inq[0]=1;d[0]=0;
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        inq[cur]=0;
         for(int i=head[cur];i!=-1;i=e[i][1])
         {
             int v=e[i][0];
             if(e[i][3]>0&&e[i][2]+d[cur]<d[v])
             {
                 d[v]=e[i][2]+d[cur];
                 prv[v]=cur;               //记录增广路
                 pre[v]=i;
                 if(!inq[v])
                 {
                     q.push(v);
                     inq[v]=1;
                 }
             }
         }
    }
     if(d[countv+1]==inf)return 0;       //无法增广
     int cur=countv+1;                   //目的点
     while(cur!=0)              //取路径上最小残流量边作为流量增广
    {
        minf=e[pre[cur]][3]<minf?e[pre[cur]][3]:minf;
        cur=prv[cur];
    }
    cur=countv+1;
    while(cur!=0)                 //增广,改流量
    {
         e[pre[cur]][3]-=minf;
         e[pre[cur]^1][3]+=minf;
         cur=prv[cur];
    }
   sumcost+=d[countv+1]*minf;         //费用为单位费用(该路径下每条边单位流量之和)*流量
   sumflow+=minf;
   return 1;
}
void mincost(int & sumcost,int & sumflow)
{
    while(spfa(sumcost,sumflow)) ;     //无法增广为止
    return ;
}
void clear()
{
    nume=countv=0;
    for(int i=0;i<=4003;i++)
      {
          head[i]=-1;
          f[i]=0;
      }
}
struct qujian
{
    int a,b,w;
};
int main()
{
   int T;
   cin>>T;
   for(int ii=1;ii<=T;ii++)
   {
       clear();
       cin>>n>>k>>m;
       int a,b,w;
       vector<int>v;
       vector<qujian>qq(n);
       for(int i=0;i<n;i++)
       {
            cin>>a>>b>>w;
            v.push_back(a);
            v.push_back(b);
            qq[i].a=a;qq[i].b=b;qq[i].w=w;
       }
       sort(v.begin(),v.end());       //从小到大处理点
       for(int i=0;i<v.size();i++)
       {
           getf(v[i]);
       }
       for(int i=0;i<n;i++)
       {
            int t1=getv(qq[i].a);
            int t2=getv(qq[i].b);
            adde(t1,t2,qq[i].w,1);  //注意点:若使用adde(getv(a),getv(b),w,1)参数是从右往左开始赋值传递的!!!
       }
         for(int i=1;i<countv;i++)
       {
            adde(i+1,i,0,inf);  //注意点:若使用adde(getv(a),getv(b),w,1)参数是从右往左开始赋值传递的!!!
       }
       adde(0,1,0,inf);adde(countv,countv+1,0,k);
        int sumcost=0;  int sumflow=0;
       mincost(sumcost,sumflow);
       cout<<"Case "<<ii<<": ";
       if(sumflow!=k)       //到不了k,无解
       {
           cout<<-1<<endl;
       }
       else
       {
           cout<<sumcost<<endl;
       }
   }
   return 0;
}