danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26237

[POJ 3723]Conscription

2016年9月19日 21:59 | Comments(0) | Category:题解 | Tags:

还是要注意读题(换言之,我英语很烂)……

这个题实际上要求求出一个最大生成森林。我们可以直接把边权造成负的,Kruskal一遍即可。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005;
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

// DJSet
int p[maxn*2],rank[maxn*2];
int find_set(int x){
	if(p[x]==x)
		return x;
	else
		return p[x]=find_set(p[x]);
}
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);
}
int n;
inline void init_set(){
	register int i;
	REP_B(i,n){
		p[i]=i;
	}
	CL_ARR(rank,0);
}

struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
int m;
Edge E[50005];
#define EDGE_ALL(i) E[i].u,E[i].v
int MST(){
	register int i,ans=0,cnt=0;
	init_set();
	sort(E+1,E+1+m);
	REP_B(i,m){
		if(!is_same(EDGE_ALL(i))){
			union_set(EDGE_ALL(i));
			ans+=E[i].d;
			cnt++;
			if(cnt==n-1)
				break;
		}
	}
	return ans;
}

int main(){
	int T,N,M;
	register int i,ans;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&N,&M,&m);
		n=N+M;
		ans=10000*n;
		for(i=1;i<=m;i++){
			scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
			E[i].u+=1;
			E[i].v+=1+N;
			E[i].d*=-1;
		}
		ans+=MST();
		printf("%d\n",ans);
	}
	return 0;
}

[POJ 2784]Buy or Build

2016年9月15日 14:00 | Comments(0) | Category:题解 | Tags:

啊这题竟然在POJ上有……

枚举套餐子集是肯定的啦,但接下来呢?有的同学或许会想直接Kruskal求MST。但是估计会T。

有一个很有效的优化:先求一遍不加套餐的MST,然后接下来每次求MST的时候都只考虑这[tex]n-1[/tex]条边,这样就很快了。

需要注意的是,这[tex]n-1[/tex]以外的边就算加入了套餐也不会被考虑。因为无论加不加套餐,这些更大的边所能连接的连通分量总是可以被以前更小的边连接,所以这条边无论如何也不会被考虑啦……

代码写起来容易让人崩溃……所以说这个题很能锻炼代码能力和Debug能力。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1005,maxq=8;
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 Cost[maxq];
vector<int> V[maxq];
struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
vector<Edge> bj;
vector<Edge> E;
vector<Edge> garbage;
int MST(int cnt,vector<Edge>& E,vector<Edge>& to){
	if(!cnt)
		return 0;
	register int i,ans=0;
	to.clear();
	for(i=0;i<E.size();i++){
		if(!is_same(E[i].u,E[i].v)){
			union_set(E[i].u,E[i].v);
			ans+=E[i].d;
			to.push_back(E[i]);
			if(!(--cnt))
				break;
		}
	}
	return ans;
}

int zb[maxn][2];
inline int EucSqr(int x,int y){
	int t1=zb[x][0]-zb[y][0],t2=zb[x][1]-zb[y][1];
	t1*=t1;
	t2*=t2;
	return t1+t2;
}
int main(){
	int T,q,num,u;
	register int i,j,k,cnt,temp,ans;
	scanf("%d%d",&n,&q);
	for(i=0;i<q;i++){
		scanf("%d%d",&num,&Cost[i]);
		V[i].clear();
		while(num--){
			scanf("%d",&u);
			V[i].push_back(u);
		}
	}
	for(i=1;i<=n;i++){
		scanf("%d%d",&zb[i][0],&zb[i][1]);
	}
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++){
			bj.push_back((Edge){i,j,EucSqr(i,j)});
		}
	init_set();
	sort(bj.begin(),bj.end());
	ans=MST(n-1,bj,E);
	for(i=0;i<(1<<q);i++){
		init_set();
		temp=0;
		cnt=n-1;
		for(j=0;j<q;j++)
			if(i&(1<<j)){
				temp+=Cost[j];
				for(k=1;k<V[j].size();k++){
					if(!is_same(V[j][k],V[j][0])){
						union_set(V[j][k],V[j][0]);
						cnt--;
					}
				}
			}
		ans=min(ans,temp+MST(cnt,E,garbage));
	}
	printf("%d\n",ans);
	return 0;
}

[BZOJ 3732]Network

2016年9月04日 11:45 | Comments(0) | Category:题解 | Tags:

这水体太热情了……和那个运输路线那个题是一样的。

本质是求最小瓶颈路。造出来MST倍增LCA维护一波即可。

代码:

/**************************************************************
    Problem: 3732
    User: danihao123
    Language: C++
    Result: Accepted
    Time:340 ms
    Memory:4344 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=15005,maxm=30005;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
 
// Graph
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
// DFS
int dep[maxn];
int anc[maxn][16],maxcost[maxn][16];
void dfs(int x,int fa,int depth,int dis){
    int i;
    dep[x]=depth;
    anc[x][0]=fa;
    maxcost[x][0]=dis;
    GRAPH_REP(i,x){
        if(to[i]!=fa){
            dfs(to[i],x,depth+1,dist[i]);
        }
    }
}
 
// Doubling LCA
int n;
inline void process(){
    register int i,j,a;
    dfs(1,-1,0,0);
    for(j=1;(1<<j)<n;j++)
        REP_B(i,n){
            if(anc[i][j-1]!=-1){
                a=anc[i][j-1];
                anc[i][j]=anc[a][j-1];
                maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
            }
        }
}
int query(int x,int y){
    register int i,j,log,ans=0;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;(1<<log)<=dep[x];log++);
    log--;
    for(j=log;j>=0;j--)
        if(dep[x]-(1<<j)>=dep[y]){
            ans=max(ans,maxcost[x][j]);
            x=anc[x][j];
        }
    if(x==y)
        return ans;
    for(j=log;j>=0;j--)
        if(anc[x][j]!=-1 && anc[x][j]!=anc[y][j]){
            ans=max(ans,max(maxcost[x][j],maxcost[y][j]));
            x=anc[x][j];
            y=anc[y][j];
        }
    ans=max(ans,max(maxcost[x][0],maxcost[y][0]));
    return ans;
}
 
// Disjoint Set
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;
    REP_B(i,n)
        p[i]=i;
    // CL_ARR(rank,0);
}
 
// MST
#define EDGE_ALL(i) E[i].u,E[i].v
struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
Edge E[maxm];
int m;
void MST(){
    register int i,cnt=0;
    init_set();
    sort(E+1,E+1+m);
    REP_B(i,m){
        if(!is_same(EDGE_ALL(i))){
            cnt++;
            union_set(EDGE_ALL(i));
            AddEdge(EDGE_ALL(i),E[i].d);
            AddEdge(E[i].v,E[i].u,E[i].d);
        }
        if(cnt==(n-1))
            break;
    }
    process();
}
 
int main(){
    int q,u,v;
    register int i;
    scanf("%d%d%d",&n,&m,&q);
    REP_B(i,m){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
    }
    MST();
    while(q--){
        scanf("%d%d",&u,&v);
        printf("%d\n",query(u,v));
    }
    return 0;
}

[POJ 1679]The Unique MST

2016年8月30日 20:27 | Comments(0) | Category:题解 | Tags:

又是一个上百行代码的题……

这个题要求判断MST的唯一性。我们可以通过求非严格的次小生成树,来判断MST的唯一性。

非严格的次小生成树就是枚举考虑将MST外的哪条边加入替换MST中的一条边。替换的方法是,求出MST中待加入边两端路径上最大边,删掉之后再把待加入边加进去。假如有一个非严格次小生成树权值和和MST一样,就说明MST不唯一。

代码:

#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=105,maxm=10005;
#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(x,v) memset(x,v,sizeof(x))

int first[maxn];
int next[205],to[205],dist[205];
int graph_cnt=0;
inline void AddEdge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
inline void ClearGraph(){
    CL_ARR(first,0);
    CL_ARR(next,0);
    CL_ARR(to,0);
    CL_ARR(dist,0);
    graph_cnt=0;
}

int anc[maxn][32],maxcost[maxn][32];
int dep[maxn];
void dfs(int x,int depth,int fa,int d){
    int i;
    dep[x]=depth;
    anc[x][0]=fa;
    maxcost[x][0]=d;
    GRAPH_REP(i,x){
        if(to[i]!=fa){
            dfs(to[i],depth+1,x,dist[i]);
        }
    }
}

int n;
inline void process(){
    register int i,j,a;
    dfs(1,0,0,0);
    for(j=1;(1<<j)<n;j++){
        REP(i,n){
            if(anc[i][j-1]!=-1){
                a=anc[i][j-1];
                anc[i][j]=anc[a][j-1];
                maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
            }
        }
    }
}

int query(int x,int y){
    register int tmp,log,i,ans=-0x7fffffff;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;(1<<log)<=dep[x];log++);
    log--;
    for(i=log;i>=0;i--)
        if(dep[x]-(1<<log)>=dep[y]){
            ans=max(ans,maxcost[x][i]);
            x=anc[x][i];
        }
    if(x==y)
        return ans;
    for(i=log;i>=0;i--)
        if(anc[x][i]!=-1 && anc[x][i]!=anc[y][i]){
            ans=max(ans,maxcost[x][i]);
            x=anc[x][i];
            ans=max(ans,maxcost[y][i]);
            y=anc[y][i];
        }
    ans=max(ans,maxcost[x][0]);
    ans=max(ans,maxcost[y][0]);
    return ans;
}

int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
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;
    REP(i,n)
        p[i]=i;
    CL_ARR(rank,0);
}

struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
#define ALL_FT(x) E[x].u,E[x].v
Edge E[maxm];
int m;
bitset<maxn> Choose;
int MST(){
    register int i,ans=0,cnt=0;
    ClearGraph();
    init_set();
    Choose.reset();
    sort(E+1,E+1+m);
    REP(i,m){
        if(!is_same(ALL_FT(i))){
            Choose[i]=true;
            cnt++;
            ans+=E[i].d;
            union_set(ALL_FT(i));
            AddEdge(ALL_FT(i),E[i].d);
            AddEdge(E[i].v,E[i].u,E[i].d);
        }
        if(cnt==(n-1)){
            break;
        }
    }
    return ans;
}
int main(){
    int T;
    int u,v,d;
    register int i,ans,temp;
    bool OK;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        REP(i,m){
            scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
        }
        ans=MST();
        CL_ARR(anc,-1);
        process();
        OK=true;
        REP(i,m){
            if(!Choose[i]){
                temp=query(ALL_FT(i));
                if(temp==E[i].d){
                    OK=false;
                    puts("Not Unique!");
                    break;
                }
            }
        }
        if(OK)
            printf("%d\n",ans);
    }
    return 0;
}

[BZOJ 1196]公路修建问题

2016年8月27日 17:06 | Comments(0) | Category:题解 | Tags:

挺简单的二分答案题……然而到现在才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 1682]干草危机

2016年6月17日 21:02 | Comments(0) | Category:题解 | Tags:

这道题就是求最小瓶颈生成树中边的最大值。

然而图的MST就是图的一个最小瓶颈生成树……这下问题就迎刃而解了。

代码:

/**************************************************************
    Problem: 1682
    User: danihao123
    Language: C++
    Result: Accepted
    Time:44 ms
    Memory:940 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<n;i++)
#define REPB(i,n) for(i=1;i<=n;i++)
#define FROMG_TO E[i].u,E[i].v
const int maxn=2001,maxm=10001;
int n,m;
// Djoint set
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
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));
}
// Graph
struct Edge{
    int u,v,d;
};
int cmp(const Edge& a,const Edge& b){
    return a.d<b.d;
}
Edge E[maxm];
int mst(){
    register int i,cnt=0,ans=0;
    init_set();
    sort(E,E+m,cmp);
    for(i=0;cnt<(n-1) && i<m;i++){
        if(!is_same(FROMG_TO)){
            union_set(FROMG_TO);
            ans=max(ans,E[i].d);
            cnt++;
        }
    }
    return ans;
}
int main(){
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
    }
    printf("%d\n",mst());
    return 0;
}

[BZOJ 1601]灌水

2016年5月14日 14:46 | Comments(0) | Category:题解 | Tags:

一定有人问我我死哪里去了……

这题挺简单的,但是对于zzs这种图论渣来讲,是巨大的困难……

这题可以造一个虚拟结点,所有点和它连该点点权长的边,其他边的正常造,然后剩下MST的就很简单了……

然而第一次写Prim……哎

代码:

[洛谷 P1967]货车运输

2016年4月10日 18:27 | Comments(0) | Category:题解 | Tags:

倍增LCA经典题……

这题的做法就是求最大生成树,然后用倍增LCA法求瓶颈路……

注意一下,两点不连通时输出-1(其实这个用并查集判断不就行了……)!!!

代码: