7 条题解

  • 2
    @ 2025-2-26 12:00:52

    这道题……可以用網絡流来解决欸!

    首先考虑可行性。

    首先建立一个超源和超汇,记为s与t; 然后在两点间建边,构成一个穿新的网络~ 最后重要的来了,很显然,从超源到超汇即s到t的最大流记为flow就是所谓的“和”——这道题的答案! 自此,证明完成,可以开始写代码了。

    要代码的看这里!!!

    接下来就是非常简单的网络流板子,顺便贴个标签,以供大家更快地“学会”网络流❤️❤️❤️

    沉浸式打板子\Huge沉浸式打板子
    #include <bits/stdc++.h>
    #define inf 2005020600
    using namespace std;
    int n,m,fir[2001],num=1,a,b;
    long long ans=0,level[2001],now[2001];
    struct g{
    	int nxt,to;
    	long long p;
    }flow[2001];
    void add(int s,int e,long long c){
    	flow[++num].to=e;
    	flow[num].nxt=fir[s];
    	flow[num].p=c;
    	fir[s]=num;
    	flow[++num].to=s;
    	flow[num].nxt=fir[e];
    	flow[num].p=0;
    	fir[e]=num;
    }
    bool bfs()
    {
    	for (int i=1;i<=m;i++){
    		level[i]=inf;
    	}
    	queue <int> q;
    	q.push(1);
    	level[1]=0;
    	now[1]=fir[1];
    	while (!q.empty()){
    		int pre=q.front();
    		q.pop();
    		for (int i=fir[pre];i;i=flow[i].nxt){
    			int go=flow[i].to;
    			if (level[go]==inf && flow[i].p>0){
    				now[go]=fir[go];
    				q.push(go);
    				level[go]=level[pre]+1;
    				if (go==m){
    					return 1;
    				}
    			}
    		}
    	}
    	return 0;
    }
    int dfs(int pos,int f) 
    {
    	if (pos==m){
    		return f;
    	}
    	int a,res=0;
    	for (int i=now[pos];i&&f;i=flow[i].nxt)
    	{
    		int go=flow[i].to;      
    		now[pos]=i;
    		if (level[go]==level[pos]+1 && flow[i].p>0){
    			a=dfs(go,fmin(flow[i].p,f));
    			if (a==0){
    				level[go]=inf;
    			}
    			f-=a;
    			res+=a;
    			flow[i].p-=a;
    			flow[i^1].p+=a;
    			}
    	}
    	return res;
    }
    int main()
    {
    	n=2,m=2;
    	cin>>a>>b;
    	add(1,2,a);
    	add(1,2,b);
    	while (bfs()){	
    		ans+=dfs(1,inf);
    	}
    	cout<<ans;
    }
    

    信息

    ID
    1
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    563
    已通过
    229
    上传者