BZOJ 屯题计划 #1

[待完善] BZOJ 2330~2335——SCOI 2011

RXDoi posted @ 2014年7月13日 20:04 in BZOJ , 292 阅读

学习大神,挖个坑,慢慢填


2330:糖果

这是我做的第一道差分约束题吧。

显然题目非常水。我借这道题理解了一下各种差分约束。

首先建图非常简单就不讲了,注意<和<=的情况。

昨天晚上我在写这道题,但是总是WA,后来百度一下题解都说最长路,我本来觉得最短路也行,大不了把边反向,权值变成相反数。今天上午YY了一下,想出了个大概。

我观察了一下正确与错误的几个数据,最短路和最长路其实其它都是一样的,唯独有区别的就是对于那些“不连通”的点的取值。

所谓“不连通”,就是指在题目中它们没有任何约束条件。那么我们从超级源点S往所有的点连一条权值为0的边就能解决。

然而这个所谓的“0”,却在最短路版和最长路版中有着不同的含义。

如果是最短路,那么最后所有的Dis都是<=0的。最后整体放大即可。对于一个“不连通点”A,显然Dis[A]=0。那么经过整体放大后Dis[A]就会变成最大值。如果是最长路,那么它就会变成最小值。

这个最大值还是最小值显然我们是无法控制的,因为我们无法知道那些点是“不连通”的,从而只能从S一视同仁地像每个点都连边0。题目中的最大最小值就体现在最长路还是最短路里。

总结一下就是:求最大值写最短路,求最小值写最长路。

这样就可以A过去了。

另外:数据奇萎无比,读入的时候一定要判断一下形如a>b,a和b是否是同一个数,是的话输出-1并打断。否则这个点会跑到6s多……

#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
  
const int Maxn=100000+19;
typedef long long LL;
struct Edge {int x,y;LL Dis;int nxt;} E[Maxn<<2];
int n,k,c,x,y,ch,E_cnt,cnt[Maxn],inQ[Maxn],Last[Maxn];
LL Dis[Maxn];
queue<int> Q;
  
inline void Read(int &x)
{
    while (!isdigit(ch=getchar()));
    x=ch-'0';
    while (isdigit(ch=getchar())) x=x*10+ch-'0';
}
inline void Add_Edge(int x,int y,LL Dis)
{
    E[E_cnt]=(Edge){x,y,Dis,Last[x]};
    Last[x]=E_cnt++;
}
inline LL SPFA()
{
    while (!Q.empty())
    {
        int x=Q.front();Q.pop();
        inQ[x]=0;
        for (int i=Last[x];i^-1;i=E[i].nxt)
        {
            int y=E[i].y;
            if (Dis[x]+E[i].Dis>Dis[y])
            {
                Dis[y]=Dis[x]+E[i].Dis;
                if (!inQ[y]) 
                {
                    inQ[y]=1;Q.push(y);
                    if (++cnt[y]>=n) return -1;
                }
            }
        }
    }
    LL Min=(1LL<<60)-1,Ans=0LL;
    for (int i=1;i<=n;i++) Min=min(Min,Dis[i]);
    for (int i=1;i<=n;i++) Dis[i]+=1-Min;
    for (int i=1;i<=n;i++) Ans+=Dis[i];
    return Ans;
}
  
int main()
{
    memset(Last,-1,sizeof(Last));
    scanf("%d%d",&n,&k);
    for (int i=0;i<k;i++)
    {
        Read(c);Read(x);Read(y);
        switch (c)
        {
            case 1:{Add_Edge(x,y,0),Add_Edge(y,x,0);break;}
            case 2:
            {
                if (x==y) {printf("-1\n");return 0;}
                Add_Edge(x,y,1);break;
            }
            case 3:{Add_Edge(y,x,0);break;}
            case 4:
            {
                if (x==y) {printf("-1\n");return 0;}
                Add_Edge(y,x,1);break;
            }
            case 5:Add_Edge(x,y,0);
        }
    }
    for (int i=1;i<=n;i++) Q.push(i),Dis[i]=0,inQ[i]=1;
    printf("%lld\n",SPFA());
}

2331:地板


2332:植物大战僵尸


2333:棘手的操作


2334:镜像拆分


2335:飞镖


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter