[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……（自带常数？）
并且注意，一定要把数组开大，开大，再开大，重要的事情说三遍
代码：
