[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查
这个是一道题啊……不过都是挺经典的问题……
建图是这样的：支持0的从[tex]S[/tex]向此点连一条容量为1的边，支持1的就向[tex]T[/tex]连一条长度为1的边，朋友之间连一条长度为1的边。跑一遍最小割即可。
这个的解释？最优情况下任何人违背自己的意见都是因为怕和朋友冲突，和朋友冲突则是因为没有违背自己的意见（废话）。所以拆了最小割就解决掉了所有冲突问题。
代码：
/**************************************************************
Problem: 2768
User: danihao123
Language: C++
Result: Accepted
Time:60 ms
Memory:7668 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=305;
namespace Dinic{
struct Edge{
int u,v,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int s,t;
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int cur[maxn],d[maxn];
bool bfs(){
register int i,u;
queue<int> Q;
memset(vis,0,sizeof(vis));
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
d[e.v]=d[u]+1;
Q.push(e.v);
vis[e.v]=true;
}
}
}
return vis[t];
}
int dfs(int x,int a){
if(x==t || a==0)
return a;
int f,flow=0;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if((d[x]+1==d[e.v]) && ((f=dfs(e.v,min(a,e.cap-e.flow)))>0)){
flow+=f;
e.flow+=f;
edges[G[x][i]^1].flow-=f;
a-=f;
if(a==0)
break;
}
}
return flow;
}
int MinCut(int S,int T){
register int ans=0;
s=S;
t=T;
while(bfs()){
memset(cur,0,sizeof(cur));
ans+=dfs(s,0x7fffffff);
}
return ans;
}
};
int main(){
int n,m;
int u,v;
register int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&u);
if(!u){
Dinic::AddEdge(0,i,1);
}else{
Dinic::AddEdge(i,n+1,1);
}
}
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
Dinic::AddEdge(u,v,1);
Dinic::AddEdge(v,u,1);
}
printf("%d\n",Dinic::MinCut(0,n+1));
return 0;
}
[BZOJ 3531]旅行
发现自己好久没写树链剖分了……唉……
言归正传，这道题很容易想到的做法就是每种宗教开一个线段树，到各个宗教的线段树里面操作即可。
很可惜，直接开线段树的话肯定会MLE。我们可以考虑动态开点，对于不需要的点一律不开。这样内存消耗量就大减了。
注意一些细节：
- 查询时判断当前结点是不是NULL。
- 删除前最好判断一下这个结点是不是NULL吧，以防万一。
- 删除操作时，如果结点没有用了，就删。但是注意，记得delete前要把原指针设为NULL，直接delete会引起悬垂指针问题导致爆炸！
代码：
/**************************************************************
Problem: 3531
User: danihao123
Language: C++
Result: Accepted
Time:10404 ms
Memory:34872 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n;
namespace SegmentTree{
struct Node{
int sumv,maxv;
Node *lc,*rc;
Node(){
sumv=maxv=0;
lc=rc=NULL;
}
void maintain(){
if(lc!=NULL){
if(rc!=NULL){
sumv=lc->sumv+rc->sumv;
maxv=max(lc->maxv,rc->maxv);
}else{
sumv=lc->sumv;
maxv=lc->maxv;
}
}else{
if(rc!=NULL){
sumv=rc->sumv;
maxv=rc->maxv;
}
}
}
};
Node* T[maxn];
int p,v;
void _Delete(Node* &o,int L,int R){
if(o==NULL)
return;
if(L==R){
Node *temp=o;
o=NULL;
delete temp;
}else{
int M=L+(R-L)/2;
if(p<=M)
_Delete(o->lc,L,M);
else
_Delete(o->rc,M+1,R);
if(o->lc==NULL && o->rc==NULL){
Node *temp=o;
o=NULL;
delete temp;
}else{
o->maintain();
}
}
}
inline void Delete(int c,int pos){
p=pos;
_Delete(T[c],1,n);
}
void _Insert(Node* &o,int L,int R){
if(o==NULL)
o=new Node();
if(L==R){
o->sumv=o->maxv=v;
}else{
int M=L+(R-L)/2;
if(p<=M)
_Insert(o->lc,L,M);
else
_Insert(o->rc,M+1,R);
}
o->maintain();
}
inline void Insert(int c,int pos,int value){
p=pos;
v=value;
_Insert(T[c],1,n);
}
int ql,qr;
int _query_max(Node *o,int L,int R){
if(o==NULL)
return 0;
if(ql<=L && R<=qr)
return o->maxv;
int M=L+(R-L)/2,ans=0;
if(ql<=M)
ans=max(ans,_query_max(o->lc,L,M));
if(qr>M)
ans=max(ans,_query_max(o->rc,M+1,R));
return ans;
}
inline int query_max(int c,int l,int r){
ql=l;
qr=r;
return _query_max(T[c],1,n);
}
int _query_sum(Node *o,int L,int R){
if(o==NULL)
return 0;
if(ql<=L && R<=qr)
return o->sumv;
int M=L+(R-L)/2,ans=0;
if(ql<=M)
ans+=_query_sum(o->lc,L,M);
if(qr>M)
ans+=_query_sum(o->rc,M+1,R);
return ans;
}
inline int query_sum(int c,int l,int r){
ql=l;
qr=r;
return _query_sum(T[c],1,n);
}
};
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_tot=0;
inline void AddEdge(int u,int v){
graph_tot++;
next[graph_tot]=first[u];
first[u]=graph_tot;
to[graph_tot]=v;
}
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
bool vis[maxn];
void dfs_1(int x,int father,int depth){
vis[x]=true;
fa[x]=father;
dep[x]=depth;
siz[x]=1;
int i,temp,max_siz=0;
GRAPH_REP(i,x){
temp=to[i];
if(!vis[temp]){
dfs_1(temp,x,depth+1);
siz[x]+=siz[temp];
if(siz[temp]>max_siz){
son[x]=temp;
max_siz=siz[temp];
}
}
}
}
int hld_cnt=0;
int rlg[maxn];
int d[maxn];
int tid[maxn],top[maxn];
void dfs_2(int x,int a){
vis[x]=true;
top[x]=a;
tid[x]=++hld_cnt;
SegmentTree::Insert(rlg[x],hld_cnt,d[x]);
if(son[x])
dfs_2(son[x],a);
else
return;
int i,temp;
GRAPH_REP(i,x){
temp=to[i];
if(!vis[temp]){
dfs_2(temp,temp);
}
}
}
int query_max(int c,int x,int y){
if(top[x]==top[y]){
if(tid[x]>tid[y])
swap(x,y);
return SegmentTree::query_max(c,tid[x],tid[y]);
}
if(dep[top[x]]<dep[top[y]])
swap(x,y);
return max(SegmentTree::query_max(c,tid[top[x]],tid[x]),query_max(c,fa[top[x]],y));
}
int query_sum(int c,int x,int y){
if(top[x]==top[y]){
if(tid[x]>tid[y])
swap(x,y);
return SegmentTree::query_sum(c,tid[x],tid[y]);
}
if(dep[top[x]]<dep[top[y]])
swap(x,y);
return SegmentTree::query_sum(c,tid[top[x]],tid[x])+query_sum(c,fa[top[x]],y);
}
inline void Replace(int pos,int direction){
int c=rlg[pos];
SegmentTree::Delete(c,tid[pos]);
SegmentTree::Insert(direction,tid[pos],d[pos]);
rlg[pos]=direction;
}
inline void Update(int pos,int v){
d[pos]=v;
SegmentTree::Insert(rlg[pos],tid[pos],v);
}
int main(){
register int i;
int q,u,v;
char buf[5];
scanf("%d%d",&n,&q);
REP_B(i,n){
scanf("%d%d",&d[i],&rlg[i]);
}
REP_B(i,n-1){
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
dfs_1(1,0,1);
memset(vis,0,sizeof(vis));
dfs_2(1,1);
while(q--){
memset(buf,0,sizeof(buf));
scanf("%s%d%d",buf,&u,&v);
if(buf[0]=='C'){
if(buf[1]=='W'){
Update(u,v);
}else{
Replace(u,v);
}
}else{
if(buf[1]=='M'){
printf("%d\n",query_max(rlg[u],u,v));
}else{
printf("%d\n",query_sum(rlg[u],u,v));
}
}
}
return 0;
}
[BZOJ 2054]疯狂的馒头
秒，秒啊……
很容易想到线段树，但是在[tex]N=10^6,M=10^7[/tex]的情况下，线段树肯定会TLE。
考虑修改，我们可以发现真正影响一个馒头颜色的只是作用于此馒头上的最后一个操作。可以考虑倒序枚举操作，然后暴力修改。但是如此暴力修改的话可能覆盖了实际时间线较晚的操作……
考虑并查集！每个节点修改完后将其父亲改为下一个点，这样的话被修改的地方就可以轻松跳过了。
注意一个细节，第[tex]N[/tex]个馒头被染色后，其父亲会被修改为[tex]N+1[/tex]，所以说并查集实际上要开[tex]N+1[/tex]！
代码：
/**************************************************************
Problem: 2054
User: danihao123
Language: C++
Result: Accepted
Time:2476 ms
Memory:39796 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1000005;
int Color[maxn];
int P[maxn];
int n;
int find_set(int x){
if(P[x]==x)
return x;
else
return P[x]=find_set(P[x]);
}
inline void init_set(){
register int i;
for(i=1;i<=(n+1);i++)
P[i]=i;
}
int buf[20];
inline void PutInt(int x){
register int i,p=0;
if(x==0){
buf[p++]=0;
}else{
while(x){
buf[p++]=x%10;
x/=10;
}
}
for(i=p-1;i>=0;i--)
putchar(buf[i]+'0');
putchar('\n');
}
int main(){
int m,p,q;
register int i,j,l,r,k=0;
bool OK=false;
scanf("%d%d%d%d",&n,&m,&p,&q);
init_set();
for(i=m;i>=1;i--){
l=(((i%n)*(p%n))%n+q%n)%n+1;
r=(((i%n)*(q%n))%n+p%n)%n+1;
if(l>r)
swap(l,r);
for(j=find_set(l);j<=r;j=find_set(j)){
Color[j]=i;
P[j]=j+1;
k++;
if(k==n){
OK=true;
break;
}
}
if(OK)
break;
}
for(i=1;i<=n;i++)
PutInt(Color[i]);
return 0;
}
[BZOJ 3436]小K的农场
差分约束系统的可行性问题啊……
按照要求连边然后SPFA判负环即可。
代码：
/**************************************************************
Problem: 3436
User: danihao123
Language: C++
Result: Accepted
Time:9224 ms
Memory:1488 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=30005;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(i,x) memset(i,x,sizeof(i))
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
int n;
namespace Graph{
int first[maxn];
int next[maxm],to[maxm];
ll dist[maxm];
int tot=0;
inline void AddEdge(int u,int v,ll d){
tot++;
next[tot]=first[u];
first[u]=tot;
to[tot]=v;
dist[tot]=d;
}
bool inQueue[maxn];
ll d[maxn];
int cnt[maxn];
bool SPFA(){
register int i,u;
queue<int> Q;
REP(i,n){
inQueue[i]=true;
Q.push(i);
}
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
GRAPH_REP(i,u){
if(d[to[i]]>d[u]+dist[i]){
d[to[i]]=d[u]+dist[i];
if(!inQueue[to[i]]){
Q.push(to[i]);
inQueue[to[i]]=true;
if(++cnt[to[i]]>n)
return false;
}
}
}
}
return true;
}
};
int main(){
int m,opt,a,b,c;
register int i;
scanf("%d%d",&n,&m);
REP(i,m){
scanf("%d%d%d",&opt,&a,&b);
if(opt==1){
scanf("%d",&c);
Graph::AddEdge(a,b,-c);
}else{
if(opt==2){
scanf("%d",&c);
Graph::AddEdge(b,a,c);
}else{
Graph::AddEdge(a,b,0);
Graph::AddEdge(b,a,0);
}
}
}
if(Graph::SPFA())
puts("Yes");
else
puts("No");
return 0;
}
[BZOJ 2330]糖果
比较裸一些的差分约束系统题……话说好像第一次写SPFA最长路啊TAT
这个题1,3,5条件直接搞就可以。2,4条件要转化成有等于号的版本。
顺便说一些这题的坑点：
- 有一个点是一个十万个点的链。在从源点连的时候，如果正序连就会炸。倒着连就不会T。
- 有的点的2,4条件出现了[tex]a=b[/tex]的情况，要特判……
- 要开long long！
代码：
/**************************************************************
Problem: 2330
User: danihao123
Language: C++
Result: Accepted
Time:356 ms
Memory:7592 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(i,x) memset(i,x,sizeof(i))
const int maxn=100005,maxm=300005;
typedef long long ll;
int first[maxn];
int next[maxm],to[maxm];
ll dist[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v,ll d){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
dist[graph_cnt]=d;
}
int n;
bool inQueue[maxn];
ll d[maxn];
int cnt[maxn];
ll SPFA(){
register int i,u;
register ll ans=0;
queue<int> Q;
CL_ARR(d,-1);
d[0]=0;
Q.push(0);
inQueue[0]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
GRAPH_REP(i,u){
if(d[u]>-1 && d[to[i]]<d[u]+dist[i]){
d[to[i]]=d[u]+dist[i];
if(!inQueue[to[i]]){
Q.push(to[i]);
inQueue[to[i]]=true;
if((++cnt[to[i]])>(n+1))
return -1;
}
}
}
}
REP(i,n){
ans+=d[i];
}
return ans;
}
int main(){
register int i;
int opt,u,v;
int k;
scanf("%d%d",&n,&k);
REP(i,k){
scanf("%d%d%d",&opt,&u,&v);
if(opt==1){
AddEdge(u,v,0);
AddEdge(v,u,0);
}else{
if(opt==2){
if(u==v){
puts("-1");
return 0;
}
AddEdge(u,v,1);
}else{
if(opt==3){
AddEdge(v,u,0);
}else{
if(opt==4){
if(u==v){
puts("-1");
}
AddEdge(v,u,1);
}else{
AddEdge(u,v,0);
}
}
}
}
}
for(i=n;i>=1;i--){
AddEdge(0,i,1);
}
printf("%lld\n",SPFA());
return 0;
}
[BZOJ 1013]球型空间产生器
不行不能颓了……线代其实刚起步……
注意每个点到球心的距离相同，距离之平方亦相同。然后假设所有半径平方为[tex]d[/tex]，那么我们先可以列出两个方程（假设[tex]n=2[/tex]，不过此时事实上可以列三个，但出于方便讨论的目的便只列两个）：
[tex](x_1-a_1)^2+(x_2-a_2)^2=d[/tex]
[tex](x_1-b_1)^2+(x_2-b_2)^2=d[/tex]
两方程作差，得：
[tex](x_1-a_1)^2+(x_2-a_2)^2-(x_1-b_1)^2-(x_2-b_2)^2=0[/tex]
整理，得：
[tex]2(b_1-a_1)x_1+2(b_2-a_2)x_2=(b_1+a_1)(b_1-a_1)+(b_2+a_2)(b_2-a_2)[/tex]
对这种方法加以推广，便可列出[tex]n[/tex]个[tex]n[/tex]元一次方程。高斯消元求解即可。
代码：
/**************************************************************
Problem: 1013
User: danihao123
Language: C++
Result: Accepted
Time:4 ms
Memory:1296 kb
****************************************************************/
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=20;
int n;
double M[maxn][maxn];
double A[maxn][maxn];
inline void Gause(){
register int i,j,k,r;
register double f;
for(i=1;i<=n;i++){
r=i;
for(j=i+1;j<=n;j++)
if(fabs(A[j][i])>fabs(A[r][i]))
r=j;
if(r!=i)
for(j=1;j<=(n+1);j++)
swap(A[r][j],A[i][j]);
for(k=i+1;k<=n;k++){
f=A[k][i]/A[i][i];
for(j=i;j<=n+1;j++)
A[k][j]-=f*A[i][j];
}
}
for(i=n;i>=1;i--){
for(j=i+1;j<=n;j++)
A[i][n+1]-=A[j][n+1]*A[i][j];
A[i][n+1]/=A[i][i];
}
}
int main(){
register int i,j;
bool flag=false;
cin>>n;
for(i=1;i<=(n+1);i++)
for(j=1;j<=n;j++)
cin>>M[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=(n+1);j++)
A[i][j]=0;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
A[i][j]=2*(M[i+1][j]-M[i][j]);
A[i][n+1]+=(M[i+1][j]-M[i][j])*(M[i+1][j]+M[i][j]);
}
}
Gause();
for(i=1;i<=n;i++){
if(flag)
putchar(' ');
flag=true;
printf("%.3f",A[i][n+1]);
}
putchar('\n');
return 0;
}
[BZOJ 1477]青蛙的约会
设用时为[tex]t[/tex]，则本题可视为解方程[tex](mt+x)-(nt+y)=kL[/tex]。
整理变形得[tex](n-m)t+Lk=x-y[/tex]。
明显需要扩欧求解。注意此题有很多细节，可参见下代码：
/**************************************************************
Problem: 1477
User: danihao123
Language: C++
Result: Accepted
Time:0 ms
Memory:1288 kb
****************************************************************/
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
if(!b)
return a;
else
return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
if(!b){
d=a;
x=1;
y=0;
}else{
exgcd(b,a%b,d,x,y);
ll t=x;
x=y;
y=t-a/b*y;
}
}
int main(){
ll a,b,c,t,M,k;
ll x,y,m,n,L;
cin>>x>>y>>m>>n>>L;
a=n-m;
b=L;
c=x-y;
k=gcd(a,b);
if(c%k!=0){
cout<<"Impossible"<<endl;
return 0;
}
a/=k;
b/=k;
c/=k;
exgcd(a,b,k,t,M);
t=(((c*t)%b)+b)%b;
if(!t)
t+=b;
cout<<t<<endl;
return 0;
}
[BZOJ 3224]普通平衡树
很好，这很interesting。
最大坑点是数可能重复。然后前驱后驱赶脚也挺坑的……
还有好像BZOJ不滋磁time(0)哎。所以我就用了wyy的生日做随机数种子辣！
代码：
/**************************************************************
Problem: 3224
User: danihao123
Language: C++
Result: Accepted
Time:376 ms
Memory:1880 kb
****************************************************************/
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct Node{
Node *ch[2];
int v;
int r;
int s;
int cnt;
Node(){
v=s=cnt=0;
r=-1;
ch[0]=ch[1]=NULL;
}
Node(int key,Node *lc,Node *rc){
v=key;
r=rand();
s=1;
cnt=1;
ch[0]=lc;
ch[1]=rc;
}
void maintain(){
s=ch[0]->s+ch[1]->s+cnt;
}
};
struct Treap{
Node *null,*root;
Treap(){
null=new Node();
root=null;
}
void rotate(Node* &o,int d){
Node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o->maintain();
k->maintain();
o=k;
}
void insert(Node* &o,int x){
if(o==null){
o=new Node(x,null,null);
}else{
if(o->v==x){
o->cnt++;
o->s++;
}else{
int d=x>(o->v);
insert(o->ch[d],x);
if(((o->ch[d])->r)>(o->r))
rotate(o,d^1);
}
}
o->maintain();
}
void del(Node* &o,int x){
if(o->v==x){
if(o->cnt>1){
o->cnt--;
o->s--;
}else{
if(o->ch[0]==null){
Node *u=o;
o=o->ch[1];
delete u;
}else{
if(o->ch[1]==null){
Node *u=o;
o=o->ch[0];
delete u;
}else{
int d=(o->ch[1]->r)>(o->ch[0]->r);
rotate(o,d^1);
del(o->ch[d^1],x);
}
}
}
}else{
int d=x>(o->v);
del(o->ch[d],x);
}
if(o!=null)
o->maintain();
}
int kth(Node *o,int k){
if(k<=(o->ch[0]->s)){
return kth(o->ch[0],k);
}else{
k-=o->ch[0]->s;
if(k<=o->cnt)
return o->v;
else
return kth(o->ch[1],k-(o->cnt));
}
}
int rank(Node *o,int x){
if(o==null)
return 0;
if(x<(o->v)){
return rank(o->ch[0],x);
}else{
if(x==o->v)
return o->ch[0]->s+1;
else
return o->ch[0]->s+o->cnt+rank(o->ch[1],x);
}
}
int pre(int x){
Node *cur=root;
int ans=0;
while(cur!=null){
if(cur->v<x){
ans=cur->v;
cur=cur->ch[1];
}else{
cur=cur->ch[0];
}
}
return ans;
}
int suc(int x){
Node *cur=root;
int ans=0;
while(cur!=null){
if(cur->v>x){
ans=cur->v;
cur=cur->ch[0];
}else{
cur=cur->ch[1];
}
}
return ans;
}
};
int main(){
int n;
int opt,x;
Treap T;
scanf("%d",&n);
srand(20020601);
while(n--){
scanf("%d%d",&opt,&x);
if(opt==1){
T.insert(T.root,x);
}else{
if(opt==2){
T.del(T.root,x);
}else{
if(opt==3){
printf("%d\n",T.rank(T.root,x));
}else{
if(opt==4){
printf("%d\n",T.kth(T.root,x));
}else{
if(opt==5){
printf("%d\n",T.pre(x));
}else{
printf("%d\n",T.suc(x));
}
}
}
}
}
}
return 0;
}
[BZOJ 1196]公路修建问题
挺简单的二分答案题……然而到现在才A
思路很明显，直接二分最终答案。那么判定如何做呢？
假设判定谓词为[tex]C(x)[/tex]，那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边（当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响）。然后白边加的不够[tex]k[/tex]谓词就是假了。
然后再考虑黑边，接下来的事情就很简单了。
代码：
/**************************************************************
Problem: 1196
User: danihao123
Language: C++
Result: Accepted
Time:672 ms
Memory:1212 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
struct Edge{
int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
return x.d2<y.d2;
}
int n;
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
register int i;
for(i=1;i<=n;i++)
p[i]=i;
memset(rank,0,sizeof(rank));
}
int k,m;
Edge E[maxm];
inline bool check(int x){
register int i,first_cnt=0,cnt=0;
init_set();
sort(E,E+m,cmp1);
REP(i,m){
if(E[i].d1>x){
break;
}else{
if(!is_same(E[i].u,E[i].v)){
first_cnt++;
cnt++;
union_set(E[i].u,E[i].v);
}
}
if(cnt==n-1){
return true;
}
}
if(first_cnt<k)
return false;
sort(E,E+m,cmp2);
REP(i,m){
if(E[i].d2>x){
break;
}else{
if(!is_same(E[i].u,E[i].v)){
cnt++;
union_set(E[i].u,E[i].v);
}
}
if(cnt==n-1)
return true;
}
return false;
}
int main(){
register int i,L=1,M,R=0;
scanf("%d%d%d",&n,&k,&m);
m--;
REP(i,m){
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
R=max(R,E[i].d1);
}
R++;
while(L<R){
M=L+(R-L)/2;
if(check(M))
R=M;
else
L=M+1;
}
printf("%d\n",L);
return 0;
}
[BZOJ 4326]运输计划
很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的，有点吃不消，再加上会被卡常，咔嚓掉。
考虑二分答案。我们可以直接二分最终答案，那么如何验证？
假设验证谓词为[tex]C(t)[/tex]，表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。
那么如何求交集呢？可以考虑树上差分，对于每次计划[tex](u,v)[/tex]，我们求出其最近公共祖先[tex]L[/tex]，然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一，对[tex]d[L][/tex]则减二。随后将d上标记上推，可以求出每个点连向父亲的边被几个计划经过。易求交集。
至此方向已明确：二分答案，树上差分验证，同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法，倍增也可。
代码：
/**************************************************************
Problem: 4326
User: danihao123
Language: C++
Result: Accepted
Time:4756 ms
Memory:62188 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
int n;
namespace FastIO{
char buf[BUFSIZE];
int IO_tot=0;
inline void InitFastIO(){
fread(buf,sizeof(char),BUFSIZE-1,stdin);
}
inline char GetC(){
return buf[IO_tot++];
}
inline int readint(){
register int x=0;
register char c=GetC();
while(!isdigit(c))
c=GetC();
while(isdigit(c)){
x=10*x+c-'0';
c=GetC();
}
return x;
}
int bf[10];
inline void putint(int x){
register int siz=0,i;
if(!x){
bf[siz++]=0;
}else{
while(x){
bf[siz++]=x%10;
x/=10;
}
}
for(i=siz-1;i>=0;i--)
putchar(bf[i]+'0');
putchar('\n');
}
};
namespace Tree{
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int tot=0;
inline void Add_Edge(int u,int v,int d){
tot++;
next[tot]=first[u];
first[u]=tot;
to[tot]=v;
dist[tot]=d;
}
int d[maxn],father[maxn];
vector<int> hx;
void dfs_1(int x,int fa,int dis){
d[x]=dis;
father[x]=fa;
int i;
GRAPH_REP(i,x){
if(to[i]!=fa)
dfs_1(to[i],x,dis+dist[i]);
}
hx.push_back(x);
}
int lazy[maxn];
inline void ClearLazy(){
memset(lazy,0,sizeof(lazy));
}
inline int DealCheck(int x){
register int i,v,ans=0;
REP_B(i,n){
v=hx[i-1];
lazy[father[v]]+=lazy[v];
}
REP_B(i,n){
if(lazy[i]==x){
ans=max(ans,d[i]-d[father[i]]);
}
}
return ans;
}
// Djoin Set
int p[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
inline void union_set(int x,int y){
p[find_set(y)]=find_set(x);
}
inline void make_set(int x){
p[x]=x;
}
// LCA
struct Query{
int u,v,b;
};
bool vis[maxn];
vector<Query> qs;
vector<int> querys[maxn];
inline void Add_Query(int x,int y,int b){
querys[x].push_back(qs.size());
qs.push_back((Query){x,y,b});
}
int res[maxn][3];
int n;
void LCA(int u){
make_set(u);
vis[u]=true;
int i,temp;
REP(i,querys[u].size()){
Query& tep=qs[querys[u][i]];
if(vis[tep.v])
res[tep.b][2]=find_set(tep.v);
}
for(i=first[u];i;i=next[i]){
temp=to[i];
if(!vis[temp]){
LCA(temp);
union_set(u,temp);
}
}
}
};
using namespace FastIO;
struct Deal{
int u,v,lca,d;
bool operator <(const Deal& x) const{
return d<x.d;
}
};
vector<Deal> V;
int m;
inline bool Check(int x){
register int i,ideal=0,yh=V[m-1].d;
Tree::ClearLazy();
for(i=m-1;i>=0;i--){
int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
if(d>x){
ideal++;
Tree::lazy[u]++;
Tree::lazy[v]++;
Tree::lazy[lca]-=2;
}else{
break;
}
}
yh-=Tree::DealCheck(ideal);
return yh<=x;
}
int main(){
register int i,u,v,lca,d;
FastIO::InitFastIO();
n=readint();
m=readint();
REP(i,n-1){
u=readint();
v=readint();
d=readint();
Tree::Add_Edge(u,v,d);
Tree::Add_Edge(v,u,d);
}
REP(i,m){
u=readint();
v=readint();
Tree::Add_Query(u,v,i);
Tree::Add_Query(v,u,i);
Tree::res[i][0]=u;
Tree::res[i][1]=v;
}
Tree::dfs_1(1,0,0);
Tree::LCA(1);
REP(i,m){
u=Tree::res[i][0];
v=Tree::res[i][1];
lca=Tree::res[i][2];
d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
V.push_back((Deal){u,v,lca,d});
}
sort(V.begin(),V.end());
u=0;
v=V[m-1].d+1;
while(u<v){
d=u+(v-u)/2;
if(Check(d))
v=d;
else
u=d+1;
}
putint(u);
return 0;
}
