7800

Galen_FuckPPT
Nan97

RyanMoriarty
yxc

YikN
bruhify
caidd

Nanfeng1997.

1746705086

sakuragod

16小时前

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110,M = (1000+N*2)*2,INF = 1e8;
int h[N],e[M],ne[M],idx;
double f[M];
int d[N],cur[N],dag[N],q[N];
PII edges[M];
int ans;
bool st[N];
int n,m,S,T;

void add(int a,int b,double c1,double c2)
{
e[idx]=b,ne[idx]=h[a],f[idx] = c1,h[a]=idx++;
e[idx]=a,ne[idx]=h[b],f[idx] = c2,h[b]=idx++;
}

void build(double g)
{
memset(h, -1, sizeof h);
idx = 0;
for(int i=1;i<=n;i++)
{
}
}

bool bfs()
{
int hh = 0,tt = -1;
memset(d,-1,sizeof d);
d[S] = 0,cur[S] = h[S],q[++tt] = S;
while(hh<=tt)
{
auto t = q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int j = e[i];
if(d[j]==-1&&f[i]>0)
{
d[j] = d[t] + 1;
cur[j] = h[j];
if(j==T) return 1;
q[++tt]=j;
}
}
}
return 0;
}

double find(int u,double limit)
{
if(u==T) return limit;
double flow = 0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
cur[u] = i;
int j = e[i];
if(d[j]==d[u]+1&&f[i]>0)
{
double t = find(j,min(f[i],limit - flow));
if(t<=0) d[j] = -1;
f[i] -= t,f[i^1] += t,flow += t;
}
}
return flow;
}

double dinic(double mid)
{
build(mid);
double r = 0,flow;
while(bfs()) while(flow=find(S,INF)) r+=flow;
return r;
}

void dfs(int u)
{
st[u] = 1;
if(u!=S) ans++;
for(int i=h[u];~i;i=ne[i])
{
int j = e[i];
if(!st[j]&&f[i]>0) dfs(j);//从源点沿着正向边，能走到的所有点都是合法解中的点
}
}

int main()
{
cin>>n>>m;
S = 0,T = n + 1;
for(int i=0;i<m;i++){
int a,b;cin>>a>>b;
edges[i] = {a,b};
dag[a]++,dag[b]++;
}
double l = 0,r = m;
while(r-l>1e-8)
{
double mid = (r+l)/2;
double t = dinic(mid);
if(m*n-t>0) l = mid;
else r = mid;
}
dinic(l);
dfs(S);

if(!ans) cout<<"1\n1";
else
{
cout<<ans<<endl;
for(int i=1;i<=n;i++)
if(st[i])
cout<<i<<endl;
}
return 0;
}


$c(S,T)(最小割)+w(最大权闭合子图)=w_{v^+}(图中所有正权节点权值和)$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 55010,M = (N+1000000)*2,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
int n,m,S,T;

{
e[idx] = b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
e[idx] = a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}

bool bfs()
{
queue<int> q;
memset(d,-1,sizeof d);
d[S] = 0,cur[S] = h[S],q.push(S);
while(q.size())
{
auto t = q.front();
q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j = e[i];
if(d[j]==-1&&w[i])
{
d[j] = d[t] + 1;
cur[j] = h[j];
if(j==T) return 1;
q.push(j);
}
}
}
return 0;
}

int find(int u,int limit)
{
if(u==T) return limit;
int flow = 0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
cur[u] = i;
int j = e[i];
if(d[j]==d[u]+1&&w[i])
{
int t = find(j,min(w[i],limit-flow));
if(!t) d[j] = -1;
w[i] -= t,w[i^1] += t,flow+=t;
}
}
return flow;
}

int dinic()
{
int r = 0,flow;
while(bfs()) while(flow=find(S,INF)) r+=flow;
return r;
}

int main()
{
cin>>n>>m;
memset(h, -1, sizeof h);
S = 0,T = n + m + 1;
LL res = 0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
res+=c;
}
cout<<res - dinic()<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 510,M = (3000+N*2)*2,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
LL p[N];
PII edges[M];
int n,m,k,S,T;

void add(int a,int b,int c1,int c2)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c1,h[a]=idx++;
e[idx]=a,ne[idx]=h[b],w[idx]=c2,h[b]=idx++;
}

void build(int k)
{
memset(h,-1,sizeof h);
idx = 0;
for(int i=0;i<m;i++)
for(int i=1;i<=n;i++)
if(p[i])
{
}
}

bool bfs()
{
queue<int> q;
memset(d,-1,sizeof d);
d[S] = 0,cur[S] = h[S],q.push(S);
while(q.size())
{
auto t = q.front();
q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j = e[i];
if(d[j]==-1&&w[i])
{
d[j] = d[t] + 1;
cur[j] = h[j];
if(j==T) return 1;
q.push(j);
}
}
}
return 0;
}

int find(int u,int limit)
{
if(u==T) return limit;
int flow = 0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
cur[u] = i;
int j = e[i];
if(d[j]==d[u]+1&&w[i])
{
int t = find(j,min(w[i],limit-flow));
if(!t) d[j] = -1;
w[i] -= t,w[i^1] += t,flow += t;
}
}
return flow;
}

LL dinic(int k)
{
build(k);
int r =0,flow;
while(bfs()) while(flow=find(S,INF)) r+=flow;
return r;
}

int main()
{
cin>>n>>m;
S = 0,T = n + 1;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
edges[i]={a,b};
}
cin>>k;
while(k--)
{
int a,b;cin>>a>>b;
p[a]=b;
}
LL res = 0;
for(int i=0;i<=30;i++) res+=dinic(i)<<i;
cout<<res<<endl;
return 0;
}



#include<bits/stdc++.h>
using namespace std;
const int N = 110,M = 810,INF = 1e8;
const double eps = 1e-8;
int h[N],e[M],ne[M],w[M],idx;
double f[M];
int d[N],cur[N];
int n,m,S,T;

{
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a]=idx++;
e[idx] = a,ne[idx] = h[b],w[idx] = c,h[b]=idx++;
}

double find(int u,double limit)
{
if(u==T) return limit;
double flow = 0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
cur[u] = i;
int j = e[i];
if(d[j]==d[u]+1&&f[i]>0)
{
double t = find(j,min(f[i],limit-flow));
if(t<eps) d[j] = -1;
f[i] -= t,f[i^1] += t,flow += t;
}
}
return flow;
}

bool bfs()
{
queue<int> q;
memset(d,-1,sizeof d);
d[S] = 0,cur[S] = h[S],q.push(S);
while(q.size())
{
auto t = q.front();
q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j = e[i];
if(d[j]==-1&&f[i]>0)
{
d[j] = d[t] + 1;
cur[j] = h[j];
if(j==T) return 1;
q.push(j);
}
}
}
return 0;
}

double dinic(double mid)
{
double res = 0;
for(int i=0;i<idx;i+=2)
if(w[i]<=mid)
{
res+=w[i]-mid;
f[i] = f[i^1] = 0;
}
else f[i] = f[i^1] = w[i] - mid;
double r = 0,flow;
while(bfs()) while(flow=find(S,INF)) r+=flow;
return r + res;
}

int main()
{
cin>>n>>m>>S>>T;
memset(h, -1, sizeof h);
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
}
double l = 0,r = 1e7;
while(r-l>eps)
{
double mid = (l+r)/2;
if(dinic(mid)<0) r = mid;
else l = mid;
}
printf("%.2lf\n",r);
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 10010,M = 200010,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
int n,m,S,T;

{
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a]=idx++;
e[idx] = a,ne[idx] = h[b],w[idx] = 0,h[b]=idx++;
}

bool bfs()
{
queue<int> q;
memset(d,-1,sizeof d);
d[S] = 0,cur[S] = h[S],q.push(S);
while(q.size())
{
auto t = q.front();
q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j = e[i];
if(d[j]==-1&&w[i])
{
d[j] = d[t] + 1;
cur[j] = h[j];
if(j==T) return 1;
q.push(j);
}
}
}
return 0;
}

int find(int u,int limit)
{
if(u==T) return limit;
int flow = 0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
cur[u] = i;
int j = e[i];
if(d[j]==d[u]+1&&w[i])
{
int t = find(j,min(w[i],limit-flow));
if(!t) d[j]=-1;
w[i] -= t,w[i^1] += t,flow += t;
}
}
return flow;
}

int dinic()
{
int r = 0,flow;
while(bfs()) while(flow = find(S,INF)) r+=flow;
return r;
}

int main()
{
cin>>n>>m>>S>>T;
memset(h, -1, sizeof h);
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
}
cout<<dinic()<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int d[N];

int main()
{
int n;cin>>n;
for(int i=0;i<n;i++) cin>>d[i];
sort(d,d+n);
int ans = 0;
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n-1;j++)
{
int dist = d[j] - d[i];
int x1 = d[j] + dist,x2 = d[j] + dist*2;
int d1 = lower_bound(d,d+n,x1) - d,d2 = upper_bound(d,d+n,x2) - d;
ans+=d2-d1;
}
}
cout<<ans<<endl;
return 0;
}


1.每次顾客来了之后，如何实现，猪舍之间猪的调整。
2.如何实现顾客的次序关系

1.若从未被光顾，则直接从源点连接一条边到该顾客，容量为对应猪舍的猪的数量。
2.若已经被光顾过，则从上一个光顾的客人连一条边，容量为INF。
(可以理解为需要从一个顾客操作完之后的结果来选择)

#include<bits/stdc++.h>
using namespace std;
const int N = 110,M = 20200,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
int g[1010],last[1010];
int m,n,S,T;

{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}

bool bfs()
{
queue<int> q;
memset(d,-1,sizeof d);
d[S] = 0,cur[S] = h[S],q.push(S);
while(q.size())
{
auto t = q.front();
q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j = e[i];
if(d[j]==-1&&w[i])
{
d[j] = d[t] + 1;
cur[j] = h[j];
if(j==T) return 1;
q.push(j);
}
}
}
return 0;
}

int find(int u,int limit)
{
if(u==T) return limit;
int flow = 0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
cur[u] = i;
int j = e[i];
if(d[j]==d[u]+1&&w[i])
{
int t = find(j,min(w[i],limit-flow));
if(!t) d[j] = -1;
w[i] -= t,w[i^1] += t,flow += t;
}
}
return flow;
}

int dinic()
{
int r = 0,flow;
while(bfs()) while(flow=find(S,INF)) r+=flow;
return r;
}

int main()
{
cin>>m>>n;
memset(h, -1, sizeof h);
S = 0,T = n + 1;
for(int i=1;i<=m;i++) cin>>g[i];
for(int i=1;i<=n;i++)
{
int a;cin>>a;
while(a--)
{
int id;cin>>id;
last[id] = i;
}
int b;cin>>b;
}

cout<<dinic()<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define fi first
#define se second
const int N = 210,M = 21000,INF = 1e8;
const double eps = 1e-8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
PII p[N];
int n,S,T;
double D;

bool check(PII a,PII b)
{
double dx = a.fi - b.fi,dy = a.se - b.se;
return dx*dx + dy*dy <= D*D + eps;
}

{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}

bool bfs()
{
queue<int> q;
memset(d,-1,sizeof d);
d[S] = 0,cur[S] = h[S],q.push(S);
while(q.size())
{
auto t = q.front();
q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j = e[i];
if(d[j]==-1&&w[i])
{
d[j] = d[t] + 1;
cur[j] = h[j];
if(j==T) return 1;
q.push(j);
}
}
}
return 0;
}

int find(int u,int limit)
{
if(u==T) return limit;
int flow = 0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
cur[u]  = i;
int j = e[i];
if(d[j]==d[u]+1&&w[i])
{
int t = find(j,min(w[i],limit-flow));
if(!t) d[j] = -1;
w[i] -= t,w[i^1] += t,flow+=t;
}
}
return flow;
}

int dinic()
{
int r = 0,flow;
while(bfs()) while(flow = find(S,INF)) r+=flow;
return r;
}

int main()
{
int Case;
scanf("%d",&Case);
while(Case--)
{
scanf("%d%lf",&n,&D);
memset(h, -1, sizeof h);
idx=0,S=0;
int tot = 0;
for(int i=1;i<=n;i++)
{
int x,y,a,b;
scanf("%d%d%d%d",&x,&y,&a,&b);
tot+=a;
p[i] = {x,y};
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(check(p[i],p[j]))
{
}
int cnt = 0;
for(int i=1;i<=n;i++)
{
T = i;
for(int i=0;i<idx;i+=2)
{
w[i] += w[i^1];
w[i^1] = 0;
}
if(dinic()==tot)
{
printf("%d ",i-1);
cnt++;
}
}
if(cnt) puts("");
else puts("-1");
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 1010,M = 251010,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
int f[N],g[N];
int n,s,S,T;

{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}

bool bfs()
{
queue<int> q;
memset(d,-1,sizeof d);
d[S] = 0,cur[S] = h[S],q.push(S);
while(q.size())
{
auto t = q.front();
q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j = e[i];
if(d[j]==-1&&w[i])
{
d[j] = d[t] + 1;
cur[j] = h[j];
if(j==T) return 1;
q.push(j);
}
}
}
return 0;
}

int find(int u,int limit)
{
if(u==T) return limit;
int flow = 0;
for(int i=cur[u];~i;i=ne[i])
{
int j = e[i];
if(d[j]==d[u]+1&&w[i])
{
int t = find(j,min(w[i],limit-flow));
if(!t) d[j] = -1;
w[i] -= t,w[i^1] +=t,flow+=t;
}
}
return flow;
}

int dinic()
{
int r = 0,flow;
while(bfs()) while(flow=find(S,INF)) r+=flow;
return r;
}

int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>g[i];
memset(h, -1, sizeof h);
S = 0,T = n*2 + 1;
int s = 0;
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
if(g[i]>=g[j])
f[i]=max(f[i],f[j]+1);
for(int j=1;j<i;j++)
if(g[i]>=g[j]&&f[i]==f[j]+1)
s=max(s,f[i]);
}

for(int i=1;i<=n;i++)
if(f[i]==s)

cout<<s<<endl;
if(s==1) cout<<n<<endl<<n<<endl;
else
{
int res = dinic();
cout<<res<<endl;
for (int i = 0; i < idx; i += 2)
{
int a = e[i ^ 1], b = e[i];
if (a == S && b == 1) w[i] = INF;//从源点向第一个点连的边
else if (a == 1 && b == n + 1) w[i] = INF;//从第一个点的入点向出点连的边
else if (a == n && b == n + n) w[i] = INF;//从最后一个点的入点像出点连的边
else if (a == n + n && b == T) w[i] = INF;//从最后一个点向汇点连的边
}
cout<<res+dinic()<<endl;
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x,y,z;
cin>>n>>x>>y>>z;
map<int,int> mp,mp1,mp2;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
mp[a]++,mp[b]++;
mp1[a]++,mp2[b]++;
}
int res = 0,sum = 0,ans = 0;
//res温度低的数量，sum适宜的数量，n-sum-res高温的数量
for(auto it:mp)
{
sum+=mp1[it.first];
ans=max(ans,res*z+sum*y+(n-res-sum)*x);
res+=mp2[it.first];
sum-=mp2[it.first];
}
cout<<ans<<endl;
return 0;
}