[atAGC045E]Fragile Balls

构造一张有向图$G=([1,n],\{(a_{i},b_{i})\})$(可以有重边和自环),定义其连通块为将其看作无向图(即边无向)后分为若干个连通块

记$in_{i}$为$i$的入度(即最终盒子中球的数量)、$out_{i}$为$i$的出度(即初始盒子中球的数量),对于$in_{i}=0$的点,若$out_{i}>0$则一定无解(因为不可能使一个盒子变空),否则$in_{i}=out_{i}=0$,可以直接删除

在此基础上,考虑当$c_{i}=1$的情况,结论:无解当且仅当这张图中存在一个连通块使得其中所有点$out_{i}\le 1$且不是自环

充分性:若$out_{i}\le 1$即不能对其操作,因此需要另取一个点过来才能操作,而这个点还需要至少一次移动回原来的连通块(若不存在这样的点同样无解),因此无解

(不能是自环是因为自环不需要操作)

必要性:首先自环一定可以(不需要操作),那么必然存在一个点$x$满足$out_{x}\ge 2$

考虑当一个盒子内被移动进一个球以后, 由于$c_{i}=1$,因此这个球必然直至结束都在这里,那么对于这个位置上其他的球,可以任意移动到别的位置,重复此过程,即其能到达的所有点的球都移动完毕

将其求强连通分量,构成一张强连通分量的DAG,对于其中入度为0的强连通分量,必然存在一个点$x$满足$out_{x}\ge 2$,证明如下:

反证法,即所有点$out_{x}\le 1$,不考虑其到其他强连通分量的边后仍满足此条件,同时还有$in_{x}\ge 1$,因为其他强连通分量没有到此强连通分量的入边(入度为0)

令该强连通分量点集为$V$,由于$in_{x}\ge 1$,因此$\sum_{x\in V}out_{x}=\sum_{x\in V}in_{x}\ge |V|$,类似的又因为$out_{x}\le 1$,因此必然恰好取$|V|$,即有$in_{x}=out_{x}=1$

此时必然没有其他出边(否则$out_{x}\ge 2$),同时也没有入边,即这就是整个连通块,而不存在$out_{x}\ge 2$,与假设矛盾

选出这样的点$x$,先将其移动到强连通分量内的一点(若只有一个点$x$必然有$x$的自环,否则$x$必然能走到其余点,因此有强连通分量内的出边),根据最初结论,即可以移动到所有能到达的强连通分量(包括自身)

由于所有入度为0的强连通分量都可以选择,即能够覆盖整张图

判定完无解后,由于每一个数恰好移动一次,答案为$\sum [a_{i}\ne b_{i}]$(当$c_{i}=1$时)

接下来考虑$c_{i}$任意的情况,将所有连通块分为三类:

1.所有点出度不超过1且不是自环,这类点需要别的连通块提供1个点帮助其移动,之后其自身也可以对其他1类的连通块提供点

2.存在点出度超过1,这类点可以帮助$\sum (c_{i}-1)$个1类的连通块,需要$t$的额外代价($t$为帮助的连通块数量),特别的,若该边为自环,需要1的额外代价,因为其本来不需要移动

3.自环(指整个连通块是自环),这一类点可以帮助$c_{i}-2$个1类的连通块,需要$t+2$的额外代价

由于$\sum t$是一个常数,我们仅考虑启用第二类中的自环以及第三类的额外代价

特判第一次操作后(只能是第二类,若不存在即为-1),之后的操作都是任意的,先将非自环的用光,对于剩下的两类,同一类中显然从大到小操作,枚举个数+二分即可(可以利用单调性做到线性,但排序仍有log)

[atAGC045E]Fragile Balls
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 100005
 4 #define oo 0x3f3f3f3f
 5 vector<long long>v1,v2;
 6 int n,m,s,ans,a[N],b[N],c[N],in[N],out[N],f[N],sz[N],vis[N];
 7 long long sum;
 8 bool cmp(int x,int y){
 9     return x>y;
10 }
11 int find1(int x){
12     if (x<=0)return 0;
13     if ((!v1.size())||(v1.back()<x))return oo;
14     return lower_bound(v1.begin(),v1.end(),x)-v1.begin()+1;
15 }
16 int find2(int x){
17     if (x<=0)return 0;
18     if ((!v2.size())||(v2.back()<x))return oo;
19     return lower_bound(v2.begin(),v2.end(),x)-v2.begin()+1;
20 }
21 int find(int k){
22     if (k==f[k])return k;
23     return f[k]=find(f[k]);
24 }
25 void merge(int x,int y){
26     x=find(x),y=find(y);
27     if (x!=y)f[x]=y;
28 }
29 int main(){
30     scanf("%d%d",&n,&m);
31     for(int i=1;i<=n;i++)f[i]=i;
32     for(int i=1;i<=m;i++){
33         scanf("%d%d%d",&a[i],&b[i],&c[i]);
34         in[b[i]]++;
35         out[a[i]]++;
36         merge(a[i],b[i]);
37         ans+=(a[i]!=b[i]);
38     }
39     for(int i=1;i<=n;i++){
40         if ((!in[i])&&(out[i])){
41             printf("-1");
42             return 0;
43         }
44         sz[find(i)]++;
45         if (out[i]>1)vis[find(i)]=1;
46     }
47     bool flag=0;
48     for(int i=1;i<=m;i++)
49         if (a[i]!=b[i]){
50             sum+=c[i]-1;
51             if ((c[i]>1)&&(vis[find(a[i])]))flag=1;
52         }
53         else{
54             if (!vis[find(a[i])])v2.push_back(c[i]-2);
55             else v1.push_back(c[i]-1);
56         }
57     sort(v1.begin(),v1.end(),cmp);
58     sort(v2.begin(),v2.end(),cmp);
59     while ((v1.size())&&(!v1.back()))v1.pop_back();
60     while ((v2.size())&&(v2.back()<=0))v2.pop_back();
61     for(int i=1;i<=n;i++)
62         if ((i==f[i])&&(sz[i]>1)&&(!vis[i]))s++;
63     if (!s){
64         printf("%d",ans);
65         return 0;
66     }
67     ans+=s;
68     if (!flag){
69         if (!v1.size()){
70             printf("-1");
71             return 0;
72         }
73         ans++;
74         s-=v1[0];
75         v1.erase(v1.begin());
76     }
77     s-=sum;
78     for(int i=1;i<v1.size();i++)v1[i]+=v1[i-1];
79     for(int i=1;i<v2.size();i++)v2[i]+=v2[i-1];
80     int mn=min(find1(s),2*find2(s));
81     for(int i=0;i<v1.size();i++)
82         if (v1[i]<s)mn=min(mn,i+1+2*find2(s-v1[i]));
83     if (mn>=oo)printf("-1");
84     else printf("%d",ans+mn);
85 } 
View Code

 

上一篇:PAT A1080(部分测试点无法通过)


下一篇:如果要在标签中显示"<"或者">"等特殊字符,可以使用“&”开头,“;”结尾,中间加上字符对应的编码就可以啦。