2 条题解

  • 0
    @ 2026-4-23 9:26:22

    • 0
      @ 2026-2-7 19:24:07
      #include<bits/stdc++.h>
      using namespace std;
      const int N = 110;
      typedef long long LL;
      struct edge
      {
      	LL x,cap,rev;
      };
      vector<edge> e[N];
      int n,m,s,t;
      int d[N],it[N];
      void add(int a,int b,LL c)
      {
      	e[a].push_back({b,c,(LL)e[b].size()});
      	e[b].push_back({a,0,(LL)e[a].size() - 1});
      }
      void bfs()
      {
      	memset(d,-1,sizeof d);
      	queue<int> q;
      	d[s] = 0;
      	q.push(s);
      	while(!q.empty())
      	{
      		int u = q.front();
      		q.pop();
      		for(auto t : e[u])
      			if(t.cap > 0 && d[t.x] < 0) d[t.x] = d[u] + 1,q.push(t.x);
      	}
      }
      LL dfs(int u,LL f)
      {
      	if(u == t) return f;
      	for(int &i = it[u]; i < e[u].size(); i ++)
      	{
      		edge &t = e[u][i]; 
      		if(d[u] < d[t.x] && t.cap > 0)
      		{
      			LL d = dfs(t.x,min(f,t.cap));
      			if(d > 0)
      			{
      				t.cap -= d;
      				e[t.x][t.rev].cap += d;
      				return d;
      			}
      		}
      	}
      	return 0;
      }
      LL dinic() 
      {
      	LL flow = 0;
      	while(1)
      	{
      		bfs();
      		if(d[t] < 0) break;
      		memset(it,0,sizeof it);
      		LL d = dfs(s,1e18);
      		while(d > 0)
      		{
      			flow += d;
      			d = dfs(s,1e18);
      		}
      	}
      	return flow;
      }
      int main()
      {
      	cin>>m>>n;
      	s = 0,t = n + m + 1;
      	LL res = 0;
      	string str;
      	for(int i = 1,x,y; i <= m; i ++)
      	{
      		cin>>x;
      		add(s,i,x);
      		res += x;
      		getline(cin,str);
      		stringstream ss(str);
      		while(ss>>y) add(i,y + m,1e18);
      	}
      	for(int i = 1,x; i <= n; i ++) cin>>x,add(i + m,t,x);
      	res -= dinic();
      	for(int i = 1; i <= m; i ++)
      		if(d[i] >= 0) cout<<i<<' ';
      	cout<<'\n';
      	for(int i = 1; i <= n; i ++)
      		if(d[i + m] >= 0) cout<<i<<' ';
      	cout<<'\n';
      	cout<<res<<endl;
      	return 0;
      }
      
      • 1

      「网络流 24 题」太空飞行计划

      信息

      ID
      972
      时间
      1000ms
      内存
      256MiB
      难度
      7
      标签
      递交数
      26
      已通过
      7
      上传者