Jury Meeting CodeForces - 854D

思路：暴力枚举会议开始的那一天（只需用所有向0点飞的航班的那一天+1去枚举即可），并计算所有人此情况下去0点和从0点出来的最小花费。

具体：首先，将航班分为飞入0和飞出0两类。然后，枚举会议开始的时间p。那么，飞入0的航班只有时间<p的生效，飞出0的航班只有时间>p+k-1的生效。显然，在p变为p+1时，最多只有各一班航班生效与失效。

（听说还能二分，但是已经打了100行了，不敢再加了。。。好累）

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long LL;

 struct Flight

 {

     LL day,city,cost;

     bool operator<(const Flight& b) const

     {

         return day<b.day||(day==b.day&&city<b.city)||(day==b.day&&city==b.city&&cost<b.cost);

     }

 }ru[],chu[];

 LL num_ru,num_chu,n,m,k,maxd,ans=0x3f3f3f3f3f3f3f3f;

 LL ok_ru,ok_chu;//分别表示现有能进0城市数量与0能到城市数量

 LL now_ru,now_chu;//分别表示现有可用的进0航班与不可用的出0航班

 LL next_chu[];//表示起飞天数在第i架航班之后的与i去同一城市的cost最小的航班编号

 LL min_chu[],min_index[];//表示"现有的"去i城市的cost最小的航班cost及编号

 LL now_ru1[];//now_chu1[100100];//分别表示现在i到0所用航班与0到i所用航班//now_chu1用min_index代替

 LL ans_ru,ans_chu;//分别表示现在入0、出0的cost总量

 int main()

 {

     LL i,t1,t2,t3,t4,j;

     scanf("%I64d%I64d%I64d",&n,&m,&k);

     for(i=;i<=m;i++)

     {

         scanf("%I64d%I64d%I64d%I64d",&t1,&t2,&t3,&t4);

         if(t2==)

         {

             chu[++num_chu]=(Flight){t1,t3,t4};

         }

         else

         {

             ru[++num_ru]=(Flight){t1,t2,t4};

             maxd=max(maxd,t1);

         }

     }

     sort(chu+,chu+num_chu+);

     sort(ru+,ru+num_ru+);

     memset(min_chu,0x3f,sizeof(min_chu));

     for(i=num_chu;i>=;i--)

     {

         next_chu[i]=min_index[chu[i].city];

         if(min_chu[chu[i].city]>chu[i].cost)

         {

             min_chu[chu[i].city]=chu[i].cost;

             min_index[chu[i].city]=i;

         }

     }

     for(i=;i<=n;i++)

         if(min_index[i]!=)

         {

             ok_chu++;

             ans_chu+=chu[min_index[i]].cost;

         }

     if(ok_chu<n)

     {

         printf("-1");

         return ;

     }

     now_chu=;

     for(j=;j<=num_ru;j++)

     {

         i=ru[j].day+;

         while(ru[now_ru+].day<i&&now_ru+<=num_ru)//后来加上&&now_ru+1<=num_ru

         {

             now_ru++;

             if(now_ru1[ru[now_ru].city]==)

             {

                 now_ru1[ru[now_ru].city]=now_ru;

                 ans_ru+=ru[now_ru].cost;

                 ok_ru++;

             }

             else if(ru[now_ru1[ru[now_ru].city]].cost>ru[now_ru].cost)

             {

                 ans_ru-=ru[now_ru1[ru[now_ru].city]].cost;

                 now_ru1[ru[now_ru].city]=now_ru;

                 ans_ru+=ru[now_ru].cost;

             }

         }

         while(chu[now_chu].day<i+k&&now_chu<=num_chu)//后面加上&&now_chu<=num_chu

         {

             if(now_chu==min_index[chu[now_chu].city])

             {

                 ans_chu-=chu[now_chu].cost;

                 if(next_chu[now_chu]==)    goto aaa;

                 min_index[chu[now_chu].city]=next_chu[now_chu];

                 ans_chu+=chu[next_chu[now_chu]].cost;

             }

             now_chu++;

         }

         if(ok_ru==n&&ok_chu==n)

             ans=min(ans,ans_ru+ans_chu);

     }

     aaa:

     if(ans==0x3f3f3f3f3f3f3f3f)

         printf("-1");

     else

         printf("%I64d",ans);

     return ;

 }