Submission #1010236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010236		vjudge1	Visiting Singapore (NOI20_visitingsingapore)	C++17	0 / 100	2075 ms	1280 KiB

VisitingSingapore

#include<bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
const int maxn=900,maxm=5000,inf=777000100;
int n,m,k,ss,tt,SS,TT;
bool hasmins[maxn],hasmint[maxn];
int mins[maxn],mint[maxn];
int he[maxn],ne[maxm],to[maxm],fr[maxm],cnt=1;
int w[maxm],A[maxn],B[maxn],C[maxn];
inline void addedge(int x,int y,int z){
   	ne[++cnt]=he[x],he[x]=cnt,to[cnt]=y,w[cnt]=z,fr[cnt]=x;
   	ne[++cnt]=he[y],he[y]=cnt,to[cnt]=x,w[cnt]=0,fr[cnt]=y;
}
int dis[maxn];
int bfs(int S,int T){
	memset(dis,0,sizeof dis);
	queue<int>q;q.push(S);dis[S]=1;
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=he[x];i;i=ne[i]){
			if(w[i]&&dis[to[i]]==0){
				dis[to[i]]=dis[x]+1;
				q.push(to[i]);
			}
		}
	}
	return dis[T];
}
int cur[maxn];
ll dfs(int x,ll flow,int T){
	if(x==T||flow==0)return flow;
	ll ans=0;
	for(int i=cur[x];i&&ans<flow;i=ne[i]){
		cur[x]=i;
		if(w[i]&&dis[to[i]]==dis[x]+1){
			ll qwq=dfs(to[i],min(flow-ans,(ll)w[i]),T);
			ans+=qwq;
			w[i]-=qwq,w[i^1]+=qwq;
		}
	}
	return ans;
}
ll dinic(int S,int T){
    ll ans=0;
    while(bfs(S,T)){
    	memcpy(cur,he,sizeof cur);
    	ans+=dfs(S,inf,T);
	}
	return ans;
}
int iscut[maxm],vis[maxn];//edge id/2
void dfs(int x){
	if(vis[x])return;
	vis[x]=1;
    for(int i=he[x];i;i=ne[i]){
    	if(w[i]&&!vis[to[i]])dfs(to[i]);
	}
}
void findcut(int S,int T){
   	memset(iscut,0,sizeof iscut);
   	memset(vis,0,sizeof vis);
   	dfs(S);
   	for(int i=2;i<=cnt;i+=2){
   		if(!vis[to[i]]&&vis[fr[i]])
		iscut[i/2]=1;
	}
}

struct node{
	int c[maxn],nl;ll val;
	bool operator<(const node&a)const
    {return val>a.val;}
	void build(){
		memset(he,0,sizeof he);
		cnt=1;
		for(int i=1;i<=m;i++){
			addedge(A[i],B[i],C[i]);
		}
		addedge(SS,ss,inf);
		addedge(tt,TT,inf);
		for(int i=1;i<=nl;i++){
			if(c[i])addedge(SS,i,inf);
			else addedge(i,TT,inf);
		}
		val=dinic(SS,TT);
		memset(vis,0,sizeof vis);
	    dfs(SS);
	    for(int i=1;i<=n;i++)
	    c[i]=vis[i];
	}
	void clear(){
		memset(c,0,sizeof c);nl=val=0;
	}
};
priority_queue<node>q;
main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	scanf("%lld%lld",&ss,&tt);
	SS=n+1,TT=SS+1;
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		A[i]=a,B[i]=b,C[i]=c;
	}
	node emm,emmm;
	emm.nl=0,emm.c[ss]=1;emm.build();
	q.push(emm);
	while(--k){
		emm=q.top();q.pop();
		for(int i=emm.nl+1;i<=n;i++){
			emmm.clear(),emmm.nl=i,emmm.c[i]=1-emm.c[i];
			for(int j=1;j<i;j++)emmm.c[j]=emm.c[j];
			emmm.build(),q.push(emmm);
		}
	}
	printf("%lld\n",q.top().val);
	return 0;
}

Compilation message (stderr)

VisitingSingapore.cpp:98:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   98 | main(){
      | ^~~~
VisitingSingapore.cpp: In function 'int main()':
VisitingSingapore.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%lld%lld%lld",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%lld%lld",&ss,&tt);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%lld%lld%lld",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 0 / 13
• Subtask 7: 0 / 50