1 条题解

  • 0
    @ 2026-2-7 18:50:54
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 510;
    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>>n>>m;
    	s = 0,t = n + m + 1;
    	LL sum = 0;
    	for(int i = 1,x; i <= n; i ++) cin>>x,add(i + m,t,x),sum += x;
    	for(int i = 1,x; i <= m; i ++) cin>>x,add(s,i,x);
    	for(int i = 1; i <= n; i ++)
    		for(int j = 1; j <= m; j ++) add(j,i + m,1);
    	LL res = dinic();
    	if(res != sum)
    	{
    		cout<<0<<endl;
    		return 0;
    	}
    	cout<<1<<endl;
    	for(int i = 1; i <= n; i ++)
    	{
    		for(auto x : e[i + m])
    			if(x.cap) cout<<x.x<<' ';
    		cout<<'\n';
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    964
    时间
    5000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    6
    已通过
    5
    上传者