Tony Zhao

题目大意

给你一些居民区，给你一些发电站。每个发电站只能为一个居民区供电，需要满足一些条件才可以供电。有的发电站是未建立的，所以使用需要花钱，不使用无影响；有的发电站已经建立了，所以使用不需要花钱，不使用需要花钱拆掉。求最小花费使得每一户居民区都有一个发电站。

发电站有的使用需要花费有的不使用需要花费需要把他们统一起来。我们可以把所有发电站都拆了，使得总花费（答案）初始时便是一个值。之后如果使用就需要付出拆掉它的花费或建立它的花费。这个问题就解决了。

首先这道题十分复杂求方案不是DP就是网络流。这道题可以S向居民区连边(1,0)(流量，花费)，居民区向可行的发电站连边(1,0)，发电站向T连边(1,拆掉它的花费或建立它的花费)，之后跑一遍最消费用最大流就可以了。

但是因为点实在太多了，所以很轻松愉快就T了。所以需要考虑优化。

这个网络流图十分诡异，因为很多边都是1，所以我们考虑优化。因为只有电站到T是有边权和花费的，所以只需要选出一些电站使得：1.他们能够提供所有地区供电 2.他们的总造价最低就可以了

这是一个典型的二分图最大匹配问题，我们只需要把花费从小到大排序往图里面加，尽量保证覆盖就可以了。

需要注意的是由于这道题需要输出最小字典序，排序的时候**一定要记得加第二关键字！**我当时还想了想但是却没有写，这东西难调死了qwq

#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t,n,m,hx[1010],hy[1010],hp[1010],px[1010],py[1010],pl[1010],pp[1010],pr[1010],pf[1010],re[1010],ans,res;
int to[1000010],nex[1000010],head[1010],tot;
bool use[1010];
priority_queue<int>q;
struct powerplant{int id,price;}power[1000010];
bool cmp(powerplant tx,powerplant ty) {if(tx.price==ty.price) return tx.id<ty.id;return tx.price<ty.price;}
double cf(double tx) {return tx*tx;}
bool calc(int tx,int ty) {return cf(hx[tx]-px[ty])+cf(hy[tx]-py[ty])<=pr[ty]*1.0*pr[ty];}
void addedge(int tx,int ty) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;}
bool xyl(int pos)
{
    for(int i=head[pos];i;i=nex[i])
        if(!use[to[i]])
        {
            use[to[i]]=true;
            if(!re[to[i]]||xyl(re[to[i]]))
            {
                re[to[i]]=pos;
                return true;
            }
        }
    return false;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(head,0,sizeof head);
        memset(re,0,sizeof re);
        tot=0,ans=0,res=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i) scanf("%d%d%d",hx+i,hy+i,hp+i);
        for(int i=1;i<=m;++i) scanf("%d%d%d%d%d%d",px+i,py+i,pl+i,pp+i,pr+i,pf+i);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                if(pl[j]>=hp[i]&&calc(i,j)) addedge(j,i+m);
        for(int i=1;i<=m;++i)
        {
            if(pf[i]) ans+=pp[i];
            power[i].id=i,power[i].price=pf[i]?-pp[i]:pp[i];
        }
        sort(power+1,power+m+1,cmp);
        for(int i=1;i<=m;++i)
        {
            memset(use,false,sizeof use);
            if(xyl(power[i].id)) ans+=power[i].price,++res;
            if(res==n) break;
        }
        if(res!=n)
        {
            printf("-1\n");
            continue;
        }
        printf("%d\n",ans);
        for(int i=1;i<=n;++i)
            q.push(-re[i+m]);
        while(!q.empty())
        {
            printf("%d%c",-q.top(),q.size()==1?'\n':' ');
            q.pop();
        }
    }
    return 0;
}

BZOJ 3291 Alice与能源计划

题目大意