专项测试 图论2
T1 收藏家
n个人，m条边，每个人可以把东西传给有直接连边的人，按时间顺序进行，求1最后的最大种类数
最大流
每个人拆成m+1人
s向0时刻每个人连容量为1的边，每个人向下一时刻连容量为a[i]的边
最后时刻的1向t连容量为a[1]的边
不必拆成m个，可以只在x出现的时刻新建x
T2 旅行
设f[i]表示 i 点最大期望步数
若使f[u]最大，且u->v，那么f[v]也要保证最大，需要在拓扑序上求f
有两个限制，(x，y)删y后x也得删，且x,y同起点
当计算f[u]时
\[f_u=1+\frac{\sum_{u->v没删}f_v}{\sum_{u->v没删}1} \]01分数规划，二分答案，设剩下了k条边
\[\sum_{u->v没删}1+f_v>k* mid \]第一个限制转化一下就是，(x，y)x存在，那y也一定存在
然后就是最大权闭合子图
代码
T1
#include
#include
#include
#include
using namespace std;
#define il inline
const int N=3e3+11;
const int inf=0x7fffffff;
struct qxxx{int v,next,w;}cc[20*N];
int n,m,s,t,tot;
int last[N];
int a[N],d[N*20];
int first[N*20],now[N*20],cnt=1;
int tim[N][N];
queue dui;
il int min_(int x,int y){return x>y?y:x;}
il void qxx(int u,int v,int w){cc[++cnt]={v,first[u],w};first[u]=cnt;return;}
il void add(int u,int v,int w){qxx(u,v,w),qxx(v,u,0);/*cout<'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
bool bfs()
{
while(dui.size())dui.pop();
memset(d,0,sizeof(d));
d[s]=1;
now[s]=first[s];
int x;
dui.push(s);
while(dui.size())
{
x=dui.front();
dui.pop();
for(int i=first[x];i;i=cc[i].next)
if(cc[i].w&&!d[cc[i].v])
{
d[cc[i].v]=d[x]+1;
now[cc[i].v]=first[cc[i].v];
dui.push(cc[i].v);
if(cc[i].v==t) return 1;
}
}
return 0;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int rest=flow,i,k;
for(i=now[x];i;i=now[x]=cc[i].next)
{
if(cc[i].w&&d[cc[i].v]==d[x]+1)
{
k=dinic(cc[i].v,min_(rest,cc[i].w));
if(!k) d[cc[i].v]=0;
rest-=k;
cc[i].w-=k;
cc[i^1].w+=k;
}
if(!rest) break;
}
return flow-rest;
}
void init()
{
memset(cc,0,sizeof(cc));
memset(first,0,sizeof(first));
memset(last,0,sizeof(last));
memset(tim,0,sizeof(tim));
cnt=1;
return;
}
void solve()
{
int h=read();
while(h--)
{
init();
n=read();
m=read();
t=n+3*m+1;
s=0;
for(int i=1;i<=n;++i) a[i]=read(),tim[i][0]=i,add(s,i,1),last[i]=i;
tot=n;
for(int x,y,i=1;i<=m;++i)
{
x=read(),y=read();
tim[x][i]=++tot;
tim[y][i]=++tot;
add(last[x],tim[x][i],a[x]);
add(last[y],tim[y][i],a[y]);
qxx(tim[x][i],tim[y][i],1);
qxx(tim[y][i],tim[x][i],1);
// cout< T2
#include
using namespace std;
#define il inline
const int N=4e4+11;
const int inf=1e9;
const double eps=1e-4;
struct qxxx{int v,next;double w;}cc[N];
struct lim_{int x,y;}ed[N];
int n,m,k,s,t;
int d[N];
int rle[N];
int cd[N];
int first[N],cnt=1,now[N];
double f[N];
vector rd[N],cb[N];
vector lim[N];
il double min_(double x,double y){return x>y?y:x;}
il void qxx(int u,int v,double w){cc[++cnt]={v,first[u],w};first[u]=cnt;return;}
il void add(int u,int v,double w){qxx(u,v,w),qxx(v,u,0);return;}
il bool jud(double x){return x>eps;}
queue tp,dui;
il int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
bool bfs()
{
while(dui.size()) dui.pop();
memset(d,0,sizeof(d));
d[s]=1,now[s]=first[s];
int x;
dui.push(s);
while(dui.size())
{
x=dui.front(),dui.pop();
for(int i=first[x];i;i=cc[i].next)
if(jud(cc[i].w)&&!d[cc[i].v])
{
d[cc[i].v]=d[x]+1;
now[cc[i].v]=first[cc[i].v];
if(cc[i].v==t) return 1;
dui.push(cc[i].v);
}
}
return 0;
}
double dinic(int x,double flow)
{
if(x==t) return flow;
int i;
double rest=flow,k;
for(i=now[x];i;i=now[x]=cc[i].next)
{
if(jud(cc[i].w)&&d[cc[i].v]==d[x]+1)
{
k=dinic(cc[i].v,min_(rest,cc[i].w));
if(!jud(k)) d[cc[i].v]=0;
rest-=k;
cc[i].w-=k;
cc[i^1].w+=k;
}
if(!jud(rest)) break;
}
return flow-rest;
}
void init()
{
memset(first,0,sizeof(first));
memset(cc,0,sizeof(cc));
cnt=1,s=t=0;
return;
}
bool check(int x,double mid)
{
init();
s=0,t=cb[x].size()+1;
double maxflow=0,flow,sum=0,val=0;
for(int v,i=0;ieps) add(s,rle[v],val),sum+=val;
else add(rle[v],t,-val);
}
for(int u,v,i=0;ieps;
}
void solve(int x)
{
for(int i=0;i