danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29173

[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;
}

[BZOJ 4195]程序自动分析

2016年1月26日 14:19 | Comments(0) | Category:题解 | Tags:

看起来是道并查集水题……

可i和j最高可达1000000000,直接开个数组放注定会MLE,怎么办?

注意n最高为1000000,所以每组数据中出现的i和j最多会有2000000种,所以我们可以把i和j“映射”为不大于2000000的整数,这样就能避免MLE了!

这种技术,就是离散化

同时注意防卡常!

代码:

[BZOJ 4196]软件包管理器

2016年1月03日 13:14 | Comments(0) | Category:题解 | Tags:

终于A了!

在CodeVS,洛谷甚至UOJ上各种A

但是在BZOJ上各种TLE。BZOJ评测姬自带10倍常数?

这题处理安装很简单,一直溯到根。

删除……注意一下树剖的一些神奇性质。