danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29169

[BZOJ 1497]最大获利

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

最大权闭合图又一题……

直接造即可,不过这题有个好处就是不用输出方案……

代码:

/**************************************************************
    Problem: 1497
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1048 ms
    Memory:16084 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=55500;
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,a,b,c;
    register int i,ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&a);
        Dinic::AddEdge(i+m,m+n+1,a);
    }
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        Dinic::AddEdge(i,a+m,0x7fffffff);
        Dinic::AddEdge(i,b+m,0x7fffffff);
        Dinic::AddEdge(0,i,c);
        ans+=c;
    }
    ans-=Dinic::MinCut(0,n+m+1);
    printf("%d\n",ans);
    return 0;
}

[COGS 727]太空飞行计划

2016年9月09日 22:40 | Comments(0) | Category:题解 | Tags:

第一次做最大权闭合图……so sad

关于最大权闭合图的做法,可以参考胡伯涛前辈的《最小割模型在信息学竞赛中的应用》。不过很麻烦的事是……打印方案。

注意,割走的边要么和[tex]S[/tex]相连,要么就和[tex]T[/tex]相连。如果一条从[tex]S[/tex]到[tex]E_i[/tex]被割走了,那么就说明[tex]E_i[/tex]没有被选择;如果一条从[tex]I_i[/tex]到[tex]T[/tex]的边被割走了,那么就说明[tex]I_i[/tex]被选择了。

于是乎,Dinic最后一次造层次图的时候(这次最终将不能到达[tex]T[/tex]),如果某个点(除了[tex]S[/tex]和[tex]T[/tex])被访问到了,那个点就被选择了。

最小割的结果是所有拒绝的实验的能赚的钱及所有选用的仪器消耗的钱的和。也就是说,答案就是[tex]p[/tex]的和减去最小割。

代码:

#include <cstdio>
#include <iostream>
#include <iterator>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
using namespace std;
const int maxn=211;
const int INF=0x7fffffff;
#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))
  
struct Edge{
    int u,v,cap,flow;
};
namespace Dinic{
    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);
    }
    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 Mincut(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,INF);
        }
        return ans;
    }
};

vector<int> AnsList;
int main(){
    register int i,j,ans=0;
    int m,n,p,x;
    bool flag;
    string line;
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    freopen("shuttle.in","r",stdin);
    freopen("shuttle.out","w+",stdout);
    ostream_iterator<int> output(cout," ");
    scanf("%d %d\n",&m,&n);
    REP_B(i,m){
        getline(cin,line);
        stringstream ss(line);
        ss>>p;
        ans+=p;
        Dinic::AddEdge(0,i,p);
        while(ss>>x){
            Dinic::AddEdge(i,m+x,INF);
        }
    }
    REP_B(i,n){
        cin>>p;
        Dinic::AddEdge(i+m,n+m+1,p);
    }
    ans-=Dinic::Mincut(0,n+m+1);
    REP_B(i,m){
        if(Dinic::vis[i]){
            AnsList.push_back(i);
        }
    }
    copy(AnsList.begin(),AnsList.end(),output);
    cout<<endl;
    AnsList.clear();
    REP_B(i,n){
        if(Dinic::vis[i+m]){
            AnsList.push_back(i);
        }
    }
    copy(AnsList.begin(),AnsList.end(),output);
    cout<<endl;
    cout<<ans<<endl;
    return 0;
}

[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查

2016年9月03日 18:07 | Comments(0) | Category:题解 | Tags:

这个是一道题啊……不过都是挺经典的问题……

建图是这样的:支持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 1001]狼抓兔子

2016年2月04日 12:15 | Comments(7) | Category:题解 | Tags:

终于A了!

再给大家欣赏一下zzs这个逗比百折不挠的卡评记录(一页半慎看):

这道题就是平面图转对偶图的恶心题~frown

zzs在此列出此题坑点,望后人警觉:

  1. 最好写一个定位函数,不然点的位置很容易混。
  2. 不要用SPFA,不然会被卡。
  3. m等于1或n等于1的情况需要特判!
  4. 不要用边表,内存开销太惊人……
  5. 用邻接表的话,不要像zzs这个逗比一样开小内存……

代码: