QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#864827 | #4809. Maximum Range | lsj2009 | WA | 0ms | 12104kb | C++14 | 6.7kb | 2025-01-21 09:40:28 | 2025-01-21 09:40:28 |
Judging History
answer
#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
struct Flow {
static const int N=1e5+5,M=1e6+5;
int head[N],cur[N],len=1;
struct node {
int from,to,nxt,cap,flow;
}; node edge[M<<1];
map<PII,int> belong;
void init() {
cl(head,0); len=1;
belong.clear();
}
void print(int u,int v,int w) {
if(w==INF)
debug("%d %d inf\n",u,v);
else
debug("%d %d %d\n",u,v,w);
}
void print_edge() {
for(auto x:belong) {
int u=x.first.first,v=x.first.second,w=edge[x.second].cap;
print(u,v,w);
}
}
void add_edge(int u,int v,int w) {
int &x1=belong[make_pair(u,v)],&x2=belong[make_pair(v,u)];
edge[++len]={u,v,head[u],w,0}; head[u]=len;
x1=len;
edge[++len]={v,u,head[v],w,0}; head[v]=len;
x2=len;
}
int flow(int u,int v) {
int x=belong[make_pair(u,v)];
return edge[x].flow;
}
bool is_cut(int u,int v) {
int x=belong[make_pair(u,v)];
return edge[x].cap==edge[x].flow;
}
int d[N];
bool used[N];
bool bfs(int s,int t,int n) {
rep(i,0,n) {
used[i]=false;
d[i]=0;
}
queue<int> q;
q.push(s); used[s]=true;
while(!q.empty()) {
int u=q.front(); q.pop();
if(u==t)
return true;
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to,cap=edge[i].cap,flow=edge[i].flow;
if(!used[v]&&cap>flow) {
used[v]=true;
d[v]=d[u]+1;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int flow,int t) {
if(u==t||!flow)
return flow;
int ret=0;
for(int &i=cur[u];i;i=edge[i].nxt) {
int v=edge[i].to;
if((d[v]==d[u]+1)&&edge[i].cap>edge[i].flow) {
int delta=dfs(v,min(flow-ret,edge[i].cap-edge[i].flow),t);
ret+=delta;
edge[i].flow+=delta;
edge[i^1].flow-=delta;
if(ret==flow)
return ret;
}
}
return ret;
}
int dinic(int s,int t,int n) {
int res=0;
while(bfs(s,t,n)) {
rep(i,0,n)
cur[i]=head[i];
res+=dfs(s,INF,t);
}
return res;
}
void reset() {
rep(i,2,len)
edge[i].flow=0;
}
void reset(int u,int v,int s,int t,int n) {
dinic(u,s,n);
dinic(t,v,n);
int x=belong[make_pair(u,v)];
edge[x].cap=edge[x].flow=edge[x^1].cap=edge[x^1].flow=0;
}
void del(int u,int v) {
int x=belong[make_pair(u,v)];
edge[x].cap=edge[x].flow=edge[x^1].cap=edge[x^1].flow=0;
}
bool vis[N];
void get(int u,int n,vector<int> &vec) {
rep(i,0,n)
vis[i]=false;
vec.clear();
queue<int> q;
q.push(u);
vis[u]=true;
while(!q.empty()) {
int u=q.front(); q.pop();
vec.push_back(u);
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to,cap=edge[i].cap,flow=edge[i].flow;
if(!vis[v]&&cap!=flow) {
q.push(v);
vis[v]=true;
}
}
}
}
}; Flow g;
const int N=1e5+5;
int head[N],len;
struct node {
int to,w,nxt;
}; node edge[N<<1];
void add_edge(int u,int v,int w) {
edge[++len]={v,w,head[u]}; head[u]=len;
}
int dfn[N],low[N],p;
bool bridge[N];
void tarjan(int u,int from) {
dfn[u]=low[u]=++p;
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to,w=edge[i].w;
if(!dfn[v]) {
tarjan(v,w);
chkmin(low[u],low[v]);
if(low[v]==dfn[v])
bridge[w]=true,debug("bridge %d\n",w);
} else if(from!=w)
chkmin(low[u],dfn[v]);
}
}
vector<int> vec[N];
bool used[N];
int c;
void dfs(int u) {
used[u]=true;
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to,w=edge[i].w;
if(!bridge[w]) {
vec[c].push_back(w);
if(!used[v])
dfs(v);
}
}
}
int a[N],b[N],d[N],mne[N],mxe[N];
bool usededge[N],visedge[N];
vector<int> tmp;
void dfs1(int u) {
tmp.push_back(u);
int cnt=0;
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to,w=edge[i].w;
if(usededge[w]) {
++cnt;
if(!visedge[w]) {
visedge[w]=true;
dfs1(v);
}
}
}
assert((cnt+1)&1);
}
void solve() {
int n,m;
scanf("%d%d",&n,&m);
rep(i,1,m) {
scanf("%d%d%d",&a[i],&b[i],&d[i]);
add_edge(a[i],b[i],i);
add_edge(b[i],a[i],i);
}
rep(i,1,n) {
if(!dfn[i])
tarjan(i,0);
}
int mx=-INF;
rep(i,1,n) {
if(!used[i]) {
++c;
dfs(i);
sort(vec[c].begin(),vec[c].end());
vec[c].erase(unique(vec[c].begin(),vec[c].end()),vec[c].end());
if(vec[c].empty())
continue;
for(auto x:vec[c]) {
if(!mne[c]||d[x]<d[mne[c]])
mne[c]=x;
if(!mxe[c]||d[x]>=d[mxe[c]])
mxe[c]=x;
}
chkmax(mx,d[mxe[c]]-d[mne[c]]);
}
}
printf("%d\n",mx);
rep(i,1,c) {
if(mne[i]&&d[mxe[i]]-d[mne[i]]==mx) {
// debug("ok\n");
for(auto x:vec[i]) {
if(x!=mxe[i]&&x!=mne[i])
g.add_edge(a[x],b[x],1);
}
int s=0,t=n+1;
g.add_edge(s,a[mne[i]],1);
g.add_edge(s,b[mne[i]],1);
g.add_edge(a[mxe[i]],t,1);
g.add_edge(b[mxe[i]],t,1);
g.dinic(s,t,t);
// g.print_edge();
usededge[mne[i]]=usededge[mxe[i]]=true;
for(auto x:vec[i]) {
if(x!=mxe[i]&&x!=mne[i]) {
if(g.flow(a[x],b[x])^g.flow(b[x],a[x]))
usededge[x]=true;
}
}
dfs1(a[mne[i]]);
printf("%d\n",(int)tmp.size());
for(auto x:tmp)
printf("%d ",x);
puts("");
return;
}
}
}
bool M2;
// g++ QOJ4809.cpp -std=c++14 -Wall -O2 -o QOJ4809
signed main() {
// file_IO();
int testcase=1;
// scanf("%d",&testcase);
while(testcase--)
solve();
debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 12104kb
input:
5 7 1 2 1 1 3 -2 2 3 1 3 4 3 4 5 1 1 5 -1 2 5 2
output:
5 5 1 5 4 3 1
result:
wrong answer Edge 1-1 does not appear in original graph