[POJ 1149]PIGS

这个题是经典的网络流题目。在经过一次次的思想过滤后你会发现,这个问题的瓶颈(换猪)大可以理解为前面的顾客给后面的留一些不是?这样问题就简单多了。

按顺序整理出到访每个猪圈的顾客,对于到访每个猪圈的第一个顾客,从[tex]S[/tex]向其连一条容量为此猪圈中猪的数量的边。然后每个猪圈前面一个顾客要个给后面的留一些猪,这个可以直接连一条容量为无限大的边来表示。

最后每个顾客向[tex]T[/tex]连一条容量为其买猪数量上限的边,然后求一遍[tex]S[/tex]到[tex]T[/tex]的最大流,问题得解。

这个题还有一个优化就是,有一些边是可以合并的(比如说从[tex]S[/tex]流出的一些边是可能指向同一顾客的,同一对顾客之间的连边数可能不止1条),但是我没有做这个优化,照样A了……

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using std::vector;
using std::queue;
using std::min;
const int maxn=105,maxm=1005;
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 d[maxn];
	inline bool bfs(){
		register int i,u,siz;
		queue<int> Q;
		memset(vis,0,sizeof(vis));
		d[s]=0;
		Q.push(s);
		vis[s]=true;
		while(!Q.empty()){
			u=Q.front();Q.pop();
			siz=G[u].size();
			for(i=0;i<siz;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 cur[maxn];
	int dfs(int x,int a){
		if(x==t || a==0){
			return a;
		}
		int f,flow=0,siz=G[x].size();
		for(int& i=cur[x];i<siz;i++){
			Edge& e=edges[G[x][i]];
			if(d[e.v]==d[x]+1){
				f=dfs(e.v,min(a,e.cap-e.flow));
				if(f>0){
					flow+=f;
					e.flow+=f;
					edges[G[x][i]^1].flow-=f;
					a-=f;
					if(a==0){
						break;
					}
				}
			}
		}
		if(a>0){
			d[x]=-1;
		}
		return flow;
	}
	inline int solve(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;
	}
};
using Dinic::AddEdge;
using Dinic::solve;
int pigs[maxm];
vector<int> Use[maxm];
int main(){
	register int i,j;
	int m,n;
	scanf("%d%d",&m,&n);
	for(i=1;i<=m;i++){
		scanf("%d",&pigs[i]);
	}
	for(i=1;i<=n;i++){
		int a,b,temp;
		scanf("%d",&a);
		for(j=1;j<=a;j++){
			scanf("%d",&temp);
			Use[temp].push_back(i);
		}
		scanf("%d",&b);
		AddEdge(i,n+1,b);
	}
	for(i=1;i<=m;i++){
		AddEdge(0,Use[i][0],pigs[i]);
		int siz=Use[i].size();
		for(j=1;j<siz;j++){
			AddEdge(Use[i][j-1],Use[i][j],0x7f7f7f7f);
		}
	}
	printf("%d\n",solve(0,n+1));
	return 0;
}

[POJ 3974]Palindrome

Manacher……妙,妙啊……

这个题就要是给一个字符串,输出最大回文字串长度。Manacher即可。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000005;
char buf[maxn],s[maxn<<1];
int p[maxn<<1];
inline void FactStr(){
	register int i,j=0,n=strlen(buf);
	s[j++]='$';
	s[j++]='#';
	for(i=0;i<n;i++){
		s[j++]=buf[i];
		s[j++]='#';
	}
	s[j]='\0';
}
inline int Manachar(){
	register int i,n=strlen(s);
	register int mx=0,id;
	register int ans=-1;
	for(i=1;i<n;i++){
		if(i<mx)
			p[i]=min(p[2*id-i],mx-i);
		else
			p[i]=1;
		while(s[i-p[i]]==s[i+p[i]])
			p[i]++;
		if((p[i]+i)>mx){
			id=i;
			mx=p[i]+i;
		}
		ans=max(ans,p[i]-1);
	}
	return ans;
}
int main(){
	register int Case=0;
	while(scanf("%s",buf)==1){
		if(buf[0]=='E')
			break;
		Case++;
		FactStr();
		printf("Case %d: %d\n",Case,Manachar());
	}
	return 0;
}

[POJ 2446]Chessboard

很容易看出是二分图最大匹配,可是怎么建图呢……

我们可以考虑把一个点的横纵坐标相加,和为偶数者称之为偶数点,反之为奇数点。我们发现,每个骨牌都正好覆盖了一个奇数点和一个偶数点。于是乎就能把点分为两个集合了,建图就很方便了。

代码:

#include <cstdio>
#include <cstring>
const int maxn=35,maxm=520;
bool G[maxm][maxm];

// Hungray
int odd_cnt=0,even_cnt=0;
bool vis[maxm];
int GirlFriend[maxm];
bool DFS(int x){
    int i;
    for(i=1;i<=even_cnt;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!GirlFriend[i] || DFS(GirlFriend[i])){
                GirlFriend[i]=x;
                return true;
            }
        }
    return false;
}
inline int Hungray(){
    register int i,ans=0;
    for(i=1;i<=odd_cnt;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}

int n,m;
bool isHole[maxn][maxn];
int ct[maxn][maxn];
inline int AddPoint(int a,int b,int x,int y){
	if(ct[x][y])
		if(!isHole[x][y])
			G[ct[a][b]][ct[x][y]]=true;
}
int main(){
	int k,x,y;
	register int i,j,tot;
	scanf("%d%d%d",&m,&n,&k);
	tot=m*n-k;
	if(1&tot){
		puts("NO");
		return 0;
	}
	for(i=1;i<=k;i++){
		scanf("%d%d",&x,&y);
		isHole[y][x]=true;
	}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++){
			if(isHole[i][j])
				continue;
			if(1&(i+j)){
				ct[i][j]=++odd_cnt;
			}else{
				ct[i][j]=++even_cnt;
			}
		}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++){
			if(!isHole[i][j] && 1&(i+j)){
				AddPoint(i,j,i-1,j);
				AddPoint(i,j,i+1,j);
				AddPoint(i,j,i,j-1);
				AddPoint(i,j,i,j+1);
			}
		}
	if(Hungray()==(tot/2)){
		puts("YES");
	}else{
		puts("NO");
	}
	return 0;
}

[POJ 2406]Power Strings

循环节又一题……用KMP性质搞搞即可。

注意特判(好像是句废话),再就没啥了……

代码:

#include <cstdio>
#include <cstring>
const int maxn=1e6+5;
char P[maxn];
int f[maxn];
int main(){
	register int i,j,xhj,n;
	while(scanf("%s",P)){
		if(P[0]=='.')
			break;
		n=strlen(P);
		f[0]=f[1]=0;
		for(i=1;i<n;i++){
			j=f[i];
			while(j && P[j]!=P[i])
				j=f[j];
			f[i+1]=(P[j]==P[i]?j+1:0);
		}
		xhj=n-f[n];
		if(!(n%xhj)){
			printf("%d\n",n/xhj);
		}else{
			puts("1");
		}
	}
	return 0;
}

[POJ 2784]Buy or Build

啊这题竟然在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;
}

[POJ 2455]Secret Milking Machine

这个题要求最大边最小,很明显要二分答案。

考虑验证谓词[tex]C(x)[/tex]。我们可以将所有边权小于等于[tex]x[/tex]的边加入图,然后判断是否有[tex]T[/tex]条从1到N的不重复路径。

不过这个怎么做呢?我们可以把边加入(注意我们要加入的边都是无向边),并把容量设为1,从1到N跑一遍最大流,就是不重复路径条数。

为什么可以这样呢?每个边容量只有1,最多只能让一条路径使用并“推送”到终点,所以从1到N的最大流就是不重复路径条数辣。

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205,maxp=40005;
#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))

namespace Dinic{
	struct Edge{
		int u,v,cap,flow;
	};
    vector<Edge> edges;
    vector<int> G[maxn];
    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);
    }
	inline void ClearGraph(){
		register int i;
		edges.clear();
		m=0;
		REP(i,maxn){
			G[i].clear();
		}
	}
    bool vis[maxn];
    int d[maxn],cur[maxn];
    int s,t;
    inline bool BFS(){
        register int i,u;
        queue<int> Q;
        CL_ARR(vis,0);
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            REP(i,G[u].size()){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    vis[e.v]=1;
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,temp;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                temp=DFS(e.v,min(a,e.cap-e.flow));
                if(temp>0){
                    e.flow+=temp;
                    edges[G[x][i]^1].flow-=temp;
                    flow+=temp;
                    a-=temp;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,0x7f7f7f7f);
        }
        return ans;
    }
};

struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
Edge EdgePool[maxp];
int n,p,t;
inline bool Check(int x){
	register int i;
	Dinic::ClearGraph();
	REP_B(i,p){
		if(EdgePool[i].d>x)
			break;
		Dinic::AddEdge(EdgePool[i].u,EdgePool[i].v,1);
		Dinic::AddEdge(EdgePool[i].v,EdgePool[i].u,1);
	}
	if((Dinic::Maxflow(1,n))<t)
		return false;
	else
		return true;
}
int main(){
	register int i,L=0,M,R=0;
	scanf("%d%d%d",&n,&p,&t);
	REP_B(i,p){
		scanf("%d%d%d",&EdgePool[i].u,&EdgePool[i].v,&EdgePool[i].d);
		R=max(R,EdgePool[i].d+1);
	}
	sort(EdgePool+1,EdgePool+1+p);
	while(L<R){
		M=L+(R-L)/2;
		if(Check(M))
			R=M;
		else
			L=M+1;
	}
	printf("%d\n",L);
	return 0;
}

[POJ 1679]The Unique MST

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

这个题要求判断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;
}

[POJ 2388]Who's in the Middle

这题题面长得挺吓人的(英文……),不过就是让你求中位数……

我怀疑会有卡快排的数据,不过我用的是STL的sort(sort好像用的不是普通的快排)

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=10000;
int A[maxn];
int main(){
	register int i;
	int n;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&A[i]);
	sort(A,A+n);
	printf("%d\n",A[n>>1]);
	return 0;
}

[POJ 2104]K-th Number

我擦终于A了这题了!

主席树坑点多……

最好不要写指针主席树,不然容易TLE……(自带常数?

并且注意,一定要把数组开大,开大,再开大,重要的事情说三遍

代码:

继续阅读