P1345 [USACO5.4]奶牛的电信Telecowmunication

加错边权了

最大流==最小割,毋庸置疑

但是这个题删的是点怎么办

那就把每一个点拆成两个,一入一出,然后中间连一条流量为1的边,图上原有的为inf

源点和汇点则大小也为inf

不能删啊

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=10001;
int head[maxn];
int p=1;
struct b{
    int to;
    int ne;
    int v;
} ed[maxn*2];
void add(int f,int t,int v){
    ed[++p].ne=head[f];ed[p].to=t;ed[p].v=v;head[f]=p;
    ed[++p].ne=head[t];ed[p].to=f;ed[p].v=0;head[t]=p;
}
int znx;
#include<queue>
queue <int> q;
int inf=(1<<29);
int vis[100001];
int exf[100001];
int pre[100001];
int s,t,n,m;
int Aimee;
bool bfs(){
    while(!q.empty()){
        q.pop();
    }
    memset(vis,0,sizeof(vis));
    q.push(s);
    vis[s]=1;
    exf[s]=inf;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=ed[i].ne){
            int v=ed[i].to;
            if(ed[i].v){
                if(vis[v]) continue;
                q.push(v);
                exf[v]=min(exf[x],ed[i].v);
                pre[v]=i;
                vis[v]=1;
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
void up(){
    int now=t;
    while(now!=s){
    //  cout<<now<<endl;
        int x=pre[now];
        ed[x].v-=exf[t];
        ed[x^1].v+=exf[t];
        now=ed[x^1].to;
    }
    Aimee+=exf[t];
}
int x,y;
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        add(x*2,y*2-1,inf);
        add(y*2,x*2-1,inf);
    }
    //偶数为出奇为入 
    for(int i=1;i<=n;++i){
        if(i==s||i==t){
            add(i*2-1,2*i,inf);
        }
        add(i*2-1,i*2,1);
        //add(i*2,i*2-1,0);
    }   
    s=s*2;
    t=t*2;
    while(bfs()){
    //  cout<<"$@3";
        up();
    }
    cout<<Aimee;
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇