QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#218019#6546. Greedy Bipartite MatchingCrysflyCompile Error//C++172.9kb2023-10-17 17:23:412023-10-17 17:23:42

Judging History

你现在查看的是最新测评结果

  • [2023-10-17 17:23:42]
  • 评测
  • [2023-10-17 17:23:41]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 200005
#define inf 0x3f3f3f3f

int n,m,res[maxn];
bool del1[maxn],del[maxn];
int s,t;

namespace F{
	int n,s,t,maxflow;
	int dep[maxn],cur[maxn];
	int tot=1,head[maxn];
	struct edge{
		int to,nxt,w,pre;
	}e[maxn*6];
	void adde(int u,int v,int w){
		e[++tot]=(edge){v,head[u],w,0};
		e[head[u]].pre=tot;
		head[u]=tot;
	}
	void add(int u,int v,int w){
		adde(u,v,w);
		adde(v,u,0);
	}
	void del(int u,int i){
		if(i==head[u]) head[u]=e[i].nxt;
		else {
			int j=e[i].pre;
			e[j].nxt=e[i].nxt,e[e[i].nxt].pre=j;
		}
	}
	int q[maxn],hd,tl;
	bool bfs(int s,int t)
	{
		For(i,0,n)cur[i]=head[i],dep[i]=inf;
		dep[s]=0,q[hd=tl=1]=s;
		while(hd<=tl)
		{
			int u=q[hd++];
			for(int i=head[u];i;i=e[i].nxt)
			{
				int v=e[i].to;
				if(dep[v]==inf&&e[i].w){
					dep[v]=dep[u]+1;
					if(v==t)return 1;
					q[++tl]=v;
				}
			}
		}return dep[t]<inf;
	}
	int dfs(int u,int t,int minn)
	{
		if(!minn||u==t)return minn;
		int res=0;
		for(int i=cur[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			cur[u]=i;
			if(dep[v]!=dep[u]+1)continue;
			int flow=dfs(v,t,min(minn,e[i].w));
			if(!flow)continue;
			res+=flow,minn-=flow;
			e[i].w-=flow,e[i^1].w+=flow;
			if(!minn)break;
		}
		if(!res) dep[u]=0;
		return res;
	}
	inline int dinic(int s,int t)
	{
		int maxflow=0,flow=0;
		while(bfs(s,t))while(flow=dfs(s,t,inf))maxflow+=flow;
		return maxflow;
	}
	inline void init(int N,int S,int T){
		n=N,s=S,t=T,tot=1,maxflow=0;
		For(i,0,n)head[i]=0;
	}
}
using F::add;

int solve()
{
	int res=F::dinic(s,t);
	For(i,1,n){
		if(F::dep[i]<inf){
			for(int j=F::head[i];j;j=F::e[j].nxt){
				if(F::e[j].w){
					del[F::e[j].to]=1;
				}
			}
		}
		else del[i]=1;
	}
	For(i,n+1,n+m)
		if(F::dep[i]<inf) del[i]=1;
	For(i,1,n) if(del[i]){
		for(int j=F::head[i];j;j=F::e[j].nxt)
	//		if(del[F::e[j].to]) F::del(i,j);
	}
	For(i,1,n+m) del1[i]|=del[i],del[i]=0;
	return res;
}

signed main()
{
	n=read(),m=read();
	s=0,t=n*2+1;
	F::init(t,s,t);
	For(i,1,n)F::add(s,i,1),F::add(i+n,t,1);
	For(i,1,m){
		int c=read();
		while(c--){
			int u=read(),v=read();
			if(!del1[u] && !del1[v+n]) F::add(u,n+v,1);
		}
		res[i]=res[i-1]+solve();
	}
	For(i,1,m)cout<<res[i]<<" ";
	return 0;
}
/*

*/

详细

answer.code: In function ‘int solve()’:
answer.code:125:9: error: expected primary-expression before ‘}’ token
  125 |         }
      |         ^