結果
問題 | No.2286 Join Hands |
ユーザー |
![]() |
提出日時 | 2025-01-23 14:19:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 2,613 bytes |
コンパイル時間 | 1,936 ms |
コンパイル使用メモリ | 167,212 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-23 14:19:26 |
合計ジャッジ時間 | 3,607 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 58 |
ソースコード
#include<bits/stdc++.h>#define pow power#define ll long long#define ull unsigned long longusing namespace std;template<typename T>void read(T &x){x=0;int f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';x=x*f;}template<typename T>inline void write(T x){if(x==0){putchar('0');return;}int len=0;short c[55];if(x<0) x=-x,putchar('-');while(x) c[len++]=x%10+'0',x/=10;while(len--) putchar(c[len]);}template<typename T>void writeln(T x){write(x);putchar('\n');}template<typename T>void writesp(T x){write(x);putchar(' ');}const int N=5005;int id,T,n,m,s,t,cnt,head[N<<1];struct qwq{int v,nxt,c;}edge[N<<3];void add(int x,int y,int c){edge[++cnt]=(qwq){y,head[x],c};head[x]=cnt;}queue<int>q;int dep[N<<1],du[N];bool bfs(){while(!q.empty()) q.pop();for(int i=0;i<=2*n+1;i++) dep[i]=0;q.push(s); dep[s]=1;while(!q.empty()){int u=q.front(); q.pop();for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v,c=edge[i].c;if(dep[v]||!c) continue;dep[v]=dep[u]+1;if(v==t) return 1;q.push(v);}}return 0;}int dfs(int u,int flow){if(u==t) return flow;int rest=flow;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v,c=edge[i].c;if(dep[v]==dep[u]+1&&c){int nwfl=dfs(v,min(rest,c));if(!nwfl) dep[v]=0;edge[i].c-=nwfl;edge[i^1].c+=nwfl;rest-=nwfl;if(!rest) break;}}return flow-rest;}int main(){// freopen("aka.in","r",stdin);// freopen("aka.out","w",stdout);// read(id); read(T);T=1;while(T--){read(n); read(m);cnt=1;int gu=0;memset(head,0,sizeof(head));memset(du,0,sizeof(du));for(int i=1;i<=n;i++){add(0,i,1);add(i,0,0);add(i+n,2*n+1,1);add(2*n+1,i+n,0);}for(int i=1;i<=m;i++){int u,v;read(u),read(v);du[u]++,du[v]++;add(u,v+n,1);add(v+n,u,0);add(v,u+n,1);add(u+n,v,0);}for(int i=1;i<=n;i++){if(!du[i]) gu++;}s=0,t=2*n+1;int flow=0;while(bfs()) flow+=dfs(s,(1<<30));if(flow==n-1&&gu==1) flow--;cout<<flow*2-n<<endl;}return 0;}