网络流杂题选做

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e4+10,M=1e5+10,inf=INT_MAX;
int n,m,S,T,tot=1,head[N];
struct edge{
    int u,v,nxt,w;
}e[M<<2];
void add(int u,int v,int w){
    e[++tot].v=v;
    e[tot].u=u;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int dep[N],cur[N];
bool bfs(int S,int T){
    for(int i=1;i<=n;i++){
        dep[i]=0;
    }
    dep[S]=1;
    queue<int>q;
    q.push(S);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(!dep[v]&&w){
                dep[v]=dep[u]+1;
                if(v==T){
                    return 1;
                }
                q.push(v);
            }
        }
    }
    return 0;
}
int dfs(int u,int flow,int T){
    if(u==T){
        return flow;
    }
    int s=0;
    for(int i=cur[u];i;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v,w=e[i].w;
        if(dep[v]==dep[u]+1&&w){
            int res=dfs(v,min(flow,w),T);
            s+=res;
            flow-=res;
            e[i].w-=res;
            e[i^1].w+=res;
        }
        if(!flow){
            break;
        }
    }
    if(!s){
        dep[u]=0;
    }
    return s;
}
int dfn[N],low[N],col[N],idx,col_num,stk[N],top,in_stack[N];
void tarjan(int u){
    low[u]=dfn[u]=++idx;
    stk[++top]=u;
    in_stack[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v,w=e[i].w;
        if(!w){
            continue;
        }
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        col[u]=++col_num;
        in_stack[u]=0;
        while(stk[top]!=u){
            col[stk[top]]=col_num;
            in_stack[stk[top]]=0;
            top--;
        }
        top--;
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m),read(S),read(T);
    for(int i=1;i<=m;i++){
        int u,v,w;
        read(u),read(v),read(w);
        add(u,v,w);
        add(v,u,0);
    }
    while(bfs(S,T)){
        for(int i=1;i<=n;i++){
            cur[i]=head[i];
        }
        dfs(S,inf,T);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    for(int i=1;i<=m;i++){
        if(!e[i<<1].w){
            int u=e[i<<1].u,v=e[i<<1].v;
            if(col[u]!=col[v]){
                write_space(1);
            }
            else{
                write_space(0);
            }
            if(col[u]==col[S]&&col[v]==col[T]){
                write_endl(1);
            }
            else{
                write_endl(0);
            }
        }
        else{
            puts("0 0");
        }
    }
    return 0;
}

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=610,M=1e6+10,inf=1e9 ;
int n,m,val[N];
int id(int x,int y){
    return (x-1)*m+y;
}
vector<int>G[N],out[N];
int deg[N],vis[N],S,T,tot=1,head[N],ans;
void topo(){
    queue<int>q;
    for(int i=1;i<=n*m;i++){
        if(!deg[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        vis[u]=1;
        q.pop();
        for(auto v:G[u]){
            deg[v]--;
            if(!deg[v]){
                q.push(v);
            }
        }
    }
}
struct node{
    int v,w,nxt;
}e[M<<1];
void add(int u,int v,int w){
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int dep[N],cur[N];
bool bfs(int S,int T){
    for(int i=1;i<=T;i++){
        dep[i]=0;
    }
    queue<int>q;
    q.push(S);
    dep[S]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(w&&!dep[v]){
                dep[v]=dep[u]+1;
                if(v==T){
                    return 1;
                }
                q.push(v);
            }
        }
    }
    return 0;
}
int dfs(int u,int flow,int T){
    if(u==T){
        return flow;
    }
    int s=0;
    for(int i=cur[u];i;i=e[i].nxt){
        int v=e[i].v,w=e[i].w;
        if(w&&dep[v]==dep[u]+1){
            int res=dfs(v,min(flow,w),T);
            e[i].w-=res;
            e[i^1].w+=res;
            s+=res;
            flow-=res;
        }
        if(!flow){
            break;
        }
    }
    if(!s){
        dep[u]=0;
    }
    return s;
}
int dinic(int S,int T){
    int sum=0;
    while(bfs(S,T)){
        for(int i=1;i<=T;i++){
            cur[i]=head[i];
        }
        sum+=dfs(S,inf,T);
    }
    return sum;
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m);
    S=n*m+1,T=n*m+2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            read(val[id(i,j)]);
            int sum;
            read(sum);
            for(int k=1,x,y;k<=sum;k++){
                read(x),read(y);
                x++,y++;
                out[id(i,j)].pb(id(x,y));
                G[id(i,j)].pb(id(x,y));
                deg[id(x,y)]++;
            }
            if(j<m){
                out[id(i,j+1)].pb(id(i,j));
                G[id(i,j+1)].pb(id(i,j));
                deg[id(i,j)]++;
            }
        }
    }
    topo();
    for(int i=1;i<=n*m;i++){
        if(!vis[i]){
            continue;
        }
        if(val[i]>0){
            add(S,i,val[i]);
            add(i,S,0);
            ans+=val[i];
        }
        else{
            add(i,T,-val[i]);
            add(T,i,0);
        }
        for(auto x:out[i]){
            if(!vis[x]){
                continue;
            }
            add(x,i,inf);
            add(i,x,0);
        }
    }
    write_endl(ans-dinic(S,T));
    return 0;
}

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=110,M=1e3+10,inf=1e9;
int head[N],tot=1,n,m,S,T,val;
double max_flow;
struct edge{
    int v,nxt;
    double W,w;
}e[M<<1];
int dep[N],cur[N];
bool bfs(int S,int T){
    for(int i=1;i<=n;i++){
        dep[i]=0;
    }
    dep[S]=1;
    queue<int>q;
    q.push(S);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            double w=e[i].w;
            if(!dep[v]&&w>eps){
                dep[v]=dep[u]+1;
                if(v==T){
                    return 1;
                }
                q.push(v);
            }
        }
    }
    return 0;
}
double dfs(int u,double flow,int T){
    if(u==T){
        return flow;
    }
    double s=0;
    for(int i=cur[u];i;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v;
        double w=e[i].w;
        if(dep[v]==dep[u]+1&&w>eps){
            double res=dfs(v,min(flow,w),T);
            e[i].w-=res;
            e[i^1].w+=res;
            flow-=res;
            s+=res;
        }
        if(flow<eps){
            break;
        }
    }
    if(!s){
        dep[u]=0;
    }
    return s;
}
double dinic(int S,int T){
    double flow=0;
    while(bfs(S,T)){
        for(int i=1;i<=n;i++){
            cur[i]=head[i];
        }
        flow+=dfs(S,inf,T);
    }
    return flow;
}
void add(int u,int v,int w){
    e[++tot].v=v;
    e[tot].W=e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void add_e(int u,int v,int w){
    add(u,v,w);
    add(v,u,0);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m),read(val);
    for(int i=1,u,v,w;i<=m;i++){
        read(u),read(v),read(w);
        add_e(u,v,w);
    }
    S=1,T=n;
    max_flow=dinic(S,T);
    write_endl((int)max_flow);
    ll l=0,r=5e9,ans=0;
    while(l<=r){
        ll mid=(l+r)>>1;
        for(int i=1;i<=tot;i++){
            e[i].w=min(e[i].W,1.0*mid/100000.0);
        }
        double flow=dinic(S,T);
        if(fabs(flow-max_flow)<eps){
            r=mid-1;
            ans=mid;
        }
        else{
            l=mid+1;
        }
    }
    printf("%.6lf\n",ans/100000.0*val);
    return 0;
}