danihao123's Blog

这道题当初竟然没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;
}

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

然而图的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;
}

这题要用到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;
}

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

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

代码：

/**************************************************************
    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;
}

噫……筛法

然而……人傻自带大常数

代码：

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

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

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

然而第一次写Prim……哎

代码：

好久没写题解了……

净去颓颓颓了……

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

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

代码：

单调队列优化DP……

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

代码：

这明明不是道网络流题。

这就是道树剖题……

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

代码：