danihao123's Blog

[POJ 1149]PIGS

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

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

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

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

代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#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的时候都只考虑这 $n-1$ 条边，这样就很快了。

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

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

代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#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

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

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

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

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

代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#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不唯一。

代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

#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……（~~自带常数？~~）

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

代码：

继续阅读

[POJ 1149]PIGS

[POJ 3974]Palindrome

[POJ 2446]Chessboard

[POJ 2406]Power Strings

[POJ 2784]Buy or Build

[POJ 2455]Secret Milking Machine

[POJ 1679]The Unique MST

[POJ 2388]Who's in the Middle

[POJ 2104]K-th Number

danihao123

搜索

分类

标签云

最新评论

最新留言

神犇的Blog

RSS

功能

计数器