Poweroj - 2883 病毒侵染 （标记割边）

传送门：Poweroj - 2883

思路分析

答案是乘积形式，可以转换为对数，就变成了普通的网络流了，最后找割边计算答案就行了

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
 
namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int INF = 0x3f3f3f3f;
 
const int N=1005,M=100005;
const ll mod=1e9+7;
 
struct node {
    double w;
    int u,v,cost,next;
} e[M];
 
int head[N],dep[N],cnt=1,vis[N];
int n,m;
 
void add(int u,int v,double w,int cost) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].u=u;
    e[cnt].next=head[u];
    e[cnt].cost=cost;
    head[u]=cnt;
}
 
bool bfs(int s,int t) {
    queue<int>q;
    mem(dep,0); 
    dep[s]=1;   
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u]; i ; i=e[i].next) {
            int v=e[i].v;
            double w=e[i].w;
            if(w>0 && !dep[v]) { 
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
 
    return dep[t];
}
 
double dfs(int u,double f,int t) {
    double fl=0;
    if(u==t)
        return f;
    for(int i=head[u]; i && f ; i=e[i].next) {
        int v=e[i].v;
        if(dep[v]==dep[u]+1 && e[i].w) {  
            double nx=dfs(v,min(f,e[i].w),t);
            e[i].w-=nx;
            e[i^1].w+=nx;
            f-=nx;
            fl+=nx;
        }
    }
    if(!fl)
        dep[u]=-2;
    return fl;
 
}
 
double dinic(int s,int t) {
    double ans=0;
    while(bfs(s,t))
        ans+=dfs(s,1000000000,t); 
    return ans;
}
 
void DFS(int u){
    vis[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        double w=e[i].w;
        if(!vis[v] && w) DFS(v);
    }
}
 
 
int main() {
 
    cnt=1;
    mem(head,0);
    read(n,m);
    for(int i=0; i<m; i++) {
        int u,v,cost;
        read(u,v,cost);
        double w=log2(cost);
        add(u,v,w,cost);
        add(v,u,w,cost);
    }
    double s=dinic(1,n);
    ll ans=1;
    int flag=0;
    DFS(1);
    for(int i=2;i<=cnt;i+=2){
        int u=e[i].u;
        int v=e[i].v;
        if(vis[u]+vis[v]==1) {
            flag=1;
            ans=ans*e[i].cost%mod;
        }
    }
    if(!flag) ans=0;
    cout<<ans<<endl;
     
 
 
 
    return 0;
}