danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26244

[BZOJ 1711]吃饭

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

这道题当初竟然没A……so sad

这题的建图要这么来:吃的、喝的、牛什么的统统拉进图里(不过牛本身只能同时享受一种食物,所以说点容量为1,要拆成俩点)。对于吃的,从[tex]S[/tex]向每个吃的连一条边。喝的每个向[tex]T[/tex]连一条边。牛本身按照喜好连即可(注意要拆成俩点!)。

代码:

/**************************************************************
    Problem: 1711
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:864 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=405,INF=0x7f7f7f7f;
 
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);
    }
    bool vis[maxn];
    int d[maxn];
    int s,t;
    bool BFS(){
        register int i,x;
        queue<int> Q;
        memset(vis,0,sizeof(vis));
        d[s]=0;
        Q.push(s);
        vis[s]=true;
        while(!Q.empty()){
            x=Q.front();
            Q.pop();
            for(i=0;i<G[x].size();i++){
                Edge& e=edges[G[x][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    d[e.v]=d[x]+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 flow=0,f;
        for(int& i=cur[x];i<G[x].size();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;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        register int ans=0;
        s=S;
        t=T;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            ans+=DFS(s,INF);
        }
        return ans;
    }
};
int main(){
    int N,F,D,f,d,x;
    register int i,j,t;
    scanf("%d%d%d",&N,&F,&D);
    t=2*N+F+D+1;
    for(i=1;i<=F;i++)
        Dinic::AddEdge(0,i,1);
    for(i=2*N+F+1;i<t;i++)
        Dinic::AddEdge(i,t,1);
    for(i=1;i<=N;i++)
        Dinic::AddEdge(F+2*i-1,F+2*i,1);
    for(i=1;i<=N;i++){
        scanf("%d%d",&f,&d);
        for(j=1;j<=f;j++){
            scanf("%d",&x);
            Dinic::AddEdge(x,2*i-1+F,1);
        }
        for(j=1;j<=d;j++){
            scanf("%d",&x);
            Dinic::AddEdge(2*i+F,F+2*N+x,1);
        }
    }
    printf("%d\n",Dinic::Maxflow(0,t));
    return 0;
}

[BZOJ 1731]Layout

2016年9月04日 15:05 | Comments(0) | Category:题解 | Tags:

裸·差分约束……

不过注意一个细节:奶牛排在队伍中的顺序和它们的编号是相同的。然后就没啥难点了……

代码:

/**************************************************************
    Problem: 1731
    User: danihao123
    Language: C++
    Result: Accepted
    Time:32 ms
    Memory:1336 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1005,maxm=40010;
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
 
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
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;
}
 
const int INF=0x7f7f7f7f;
bool inQueue[maxn];
int cnt[maxn];
int d[maxn];
int n;
int SPFA(){
    register int i,u;
    queue<int> Q;
    CL_ARR(d,0x7f);
    d[1]=0;
    Q.push(1);
    inQueue[1]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        GRAPH_REP(i,u){
            if(d[u]<INF && d[u]+dist[i]<d[to[i]]){
                d[to[i]]=d[u]+dist[i];
                if(!inQueue[to[i]]){
                    Q.push(to[i]);
                    inQueue[to[i]]=true;
                    if((++cnt[to[i]])>n)
                        return -1;
                }
            }
        }
    }
    if(d[n]==INF)
        return -2;
    else
        return d[n];
}
int main(){
    int ML,MD,u,v,d;
    register int i;
    scanf("%d%d%d",&n,&ML,&MD);
    REP_B(i,ML){
        scanf("%d%d%d",&u,&v,&d);
        AddEdge(u,v,d);
    }
    REP_B(i,MD){
        scanf("%d%d%d",&u,&v,&d);
        AddEdge(v,u,-d);
    }
    printf("%d\n",SPFA());
    return 0;
}

[BZOJ 1682]干草危机

2016年6月17日 21:02 | Comments(0) | Category:题解 | Tags:

这道题就是求最小瓶颈生成树中边的最大值。

然而图的MST就是图的一个最小瓶颈生成树……这下问题就迎刃而解了。

代码:

/**************************************************************
    Problem: 1682
    User: danihao123
    Language: C++
    Result: Accepted
    Time:44 ms
    Memory:940 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<n;i++)
#define REPB(i,n) for(i=1;i<=n;i++)
#define FROMG_TO E[i].u,E[i].v
const int maxn=2001,maxm=10001;
int n,m;
// Djoint set
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;
    for(i=1;i<=n;i++)
        p[i]=i;
    // memset(rank,0,sizeof(rank));
}
// Graph
struct Edge{
    int u,v,d;
};
int cmp(const Edge& a,const Edge& b){
    return a.d<b.d;
}
Edge E[maxm];
int mst(){
    register int i,cnt=0,ans=0;
    init_set();
    sort(E,E+m,cmp);
    for(i=0;cnt<(n-1) && i<m;i++){
        if(!is_same(FROMG_TO)){
            union_set(FROMG_TO);
            ans=max(ans,E[i].d);
            cnt++;
        }
    }
    return ans;
}
int main(){
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
    }
    printf("%d\n",mst());
    return 0;
}

[BZOJ 1232]安慰奶牛

2016年6月16日 22:18 | Comments(0) | Category:题解 | Tags:

这题要用到DFS欧拉遍历树(胡编词汇)的一个特征:每一条边都经过2遍。这样似乎每个边度数就可以确定了,然后……

但是,起点也要算啊……

代码:

/**************************************************************
    Problem: 1232
    User: danihao123
    Language: C++
    Result: Accepted
    Time:248 ms
    Memory:2056 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10001,maxm=100001;
// Djoin set
int p[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void union_set(int x,int y){
    p[find_set(x)]=find_set(y);
}
bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
// Graph
struct Edge{
    int u,v,d;
};
int cmp(const Edge& a,const Edge& b){
    return a.d<b.d;
}
int n,m;
int c[maxn];
Edge E[maxm];
int mst(){
    register int i,cnt=0,ans=0;
    for(i=1;i<=n;i++)
        p[i]=i;
    sort(E,E+m,cmp);
    for(i=0;cnt<(n-1) && i<m;i++){
        if(!is_same(E[i].u,E[i].v)){
            union_set(E[i].u,E[i].v);
            ans+=E[i].d;
            cnt++;
        }
    }
    return ans;
}
int main(){
    register int i,kkk=0x5fffffff;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&c[i]);
        kkk=min(kkk,c[i]);
    }
    for(i=0;i<m;i++){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
        E[i].d+=E[i].d+c[E[i].u]+c[E[i].v];
    }
    printf("%d\n",kkk+mst());
    return 0;
}

[BZOJ 1603]打谷机

2016年6月04日 14:22 | Comments(0) | Category:题解 | Tags:

啊啊啊啊我又活过来了……

然而这也就是一道脑残题……

代码:

/**************************************************************
    Problem: 1603
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1001;
struct Edge{
    int u,v;
    bool type;
};
vector<Edge> edges;
vector<int> G[maxn];
void Add_Edge(int u,int v,bool type){
    edges.push_back((Edge){u,v,type});
    G[u].push_back(edges.size()-1);
}
bool ans[maxn],vis[maxn];
void dfs(int x){
    vis[x]=true;
    int i;
    for(i=0;i<G[x].size();i++){
        Edge& e=edges[G[x][i]];
        if(!vis[e.v]){
            ans[e.v]=e.type?(!ans[x]):ans[x];
            dfs(e.v);
        }
    }
}
int main(){
    register int i;
    int n,u,v,d;
    scanf("%d",&n);
    for(i=0;i<(n-1);i++){
        scanf("%d%d%d",&u,&v,&d);
        Add_Edge(u,v,(bool)d);
        Add_Edge(v,u,(bool)d);
    }
    dfs(1);
    printf("%d\n",ans[n]?1:0);
    return 0;
}

[BZOJ 1607]轻拍牛头

2016年5月15日 13:43 | Comments(0) | Category:题解 | Tags:

噫……筛法

然而……人傻自带大常数

代码:

[BZOJ 1601]灌水

2016年5月14日 14:46 | Comments(0) | Category:题解 | Tags:

一定有人问我我死哪里去了……

这题挺简单的,但是对于zzs这种图论渣来讲,是巨大的困难……

这题可以造一个虚拟结点,所有点和它连该点点权长的边,其他边的正常造,然后剩下MST的就很简单了……

然而第一次写Prim……哎

代码:

[BZOJ 1699]排队

2016年5月01日 11:37 | Comments(0) | Category:题解 | Tags:

好久没写题解了……

净去颓颓颓了……

这题是ST裸题,顺便复习一下ST。

那个I/O优化提示就是赤裸裸的威胁,赤裸裸的威胁啊!

代码:

[BZOJ 2442]修剪草坪

2016年2月26日 14:46 | Comments(4) | Category:题解 | Tags:

单调队列优化DP……

bi了doge了……现在才能学会一些简单的单调队列优化DP

代码:

[BZOJ 4390]Max Flow

2016年1月09日 17:45 | Comments(2) | Category:题解 | Tags:

这明明不是道网络流题。

这就是道树剖题……

没有什么太难的地方,然而还是调试了几遍才过。

代码: