一直还在用pascal做数据。。。现在终于学会了C++的随机。
首先需要
#include 写一个srand((unsigned)time(NULL)) （随机种子） 然后就可以这样用了。t=rand()%xxxx； 但是比赛的时候是不允许读时间的，所以比赛的时候直接rand()就可以得到一串随机数。但是每次运行程序的结果是一样的(但每次rand()的结果不一样)。 所以做数据对拍的时候我们可以用那个随机种子。 比赛时直接rand()就可以了。
分类存档：默认分类
线性规划与网络流之6 构图、网络流
题目参见：http://www.byvoid.com/blog/lpf24-solution/
题意：给定A[1],A[2]…A[N]
Question1：最长上升子序列的长度是多少？
Question2：从这个序列中，最多能取出多少个没有重复使用的元素的上升子序列。其长度=Question1
Question3：同2，但A[1]和A[N]能使用无限次。
分析：
第一问：DP
第二问：
对于f[i]=1的点加一条边(S,i,1)
对于f[i]=len的点加一条边(i,T,1)
对于a[j] 求最大流 第三问： 在第二问的图的基础上加入以下两条边 (S,1,INF) 如果f[n]=len，加这条边(n,T,INF) 求最大流 HINT: 1、len表示第一问的答案。 2、我的程序是从0开始的。。。和分析有点出入
code:
#include
#define N 1000000
using namespace std;
const int INF=0x7FFFFFFF/2;
struct gtp{int x,y,next,c,op;} g[E];
int n,a[500],f[500],e,ls[N],d[N],num[N],cur[N],fa[N],S,T,Flow;
int problem1(){
for (int i=0;i
for (int i=1;i
ans=max(f[i],ans);
}
return ans;
}
void add(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].c=c; g[e].op=e+1;
e++;
g[e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].c=0; g[e].op=e-1;
}
void relabel(int k){
int min=T,i=ls[k];
cur[k]=ls[k];
while (i!=0){
if (g[i].c>0 && d[g[i].y]
}
d[k]=min+1;
}
void change(){
int nf=INF;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c
for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
}
void sap(){
Flow=0;
for (int i=0;i<=T;i++){
d[i]=0;
num[i]=0;
cur[i]=ls[i];
}
num[0]=T+1;
int i=S;
while (d[S]<=T){
while (cur[i]!=0){
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
cur[i]=g[cur[i]].next;
}
if (cur[i]==0){
num[d[i]]–;
if (num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=S) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==T){
change();
i=S;
}
}
}
}
void problem2(int len){
memset(ls,0,sizeof(ls));
S=n;
T=n+1;
e=0;
for (int i=0;i
if (f[i]==len) add(i,T,1);
}
for (int i=0;i
cout << Flow << endl;
}
void problem3(int len){
memset(ls,0,sizeof(ls));
S=n;
T=n+1;
e=0;
add(S,0,INF);
if (f[n-1]==len) add(n-1,T,INF);
for (int i=0;i
if (f[i]==len) add(i,T,1);
}
for (int i=0;i
cout << Flow << endl;
}
int main(){
freopen("alis.in","r",stdin);
freopen("alis.ans","w",stdout);
scanf("%d",&n);
for (int i=0;i
cout << len << endl;
problem2(len);
problem3(len);
return 0;
}
线性规划与网络流之4 抽象模型、网络流
题目：http://www.byvoid.com/blog/lpf24-solution/
分析：
把每根柱子上按顺序插的球当做是一条路径。然后这题变成了N个不相交路径最多可以覆盖多少连续的球。我们可以枚举答案。然后每次加入一个点。然后sap。直到不能覆盖。因为每次最多增加1的流量，所以sap会非常快。平均起来也就几乎O(N)每一次
code:
#include
#define N 111111
#define sqr(x) (x)*(x)
using namespace std;
struct gtp{int x,y,next,c,op;} g[E];
int n,e=0,ls[N],S=0,T=1,p=1,Flow=0,cur[N],fa[N],d[N],num[N];
inline void add(int X,int Y,int C){
e++;
g[e].x=X; g[e].y=Y; g[e].c=C; g[e].op=e+1; g[e].next=ls[X]; ls[X]=e;
e++;
g[e].x=Y; g[e].y=X; g[e].c=0; g[e].op=e-1; g[e].next=ls[Y]; ls[Y]=e;
}
void relabel(int k){
int i,min=p;
cur[k]=ls[k];
i=ls[k];
while (i>0){
if (g[i].c>0 && d[g[i].y]
}
d[k]=min+1;
}
void change(){
int i;
i=T;
while (i!=S){
g[fa[i]].c–;
g[g[fa[i]].op].c++;
i=g[fa[i]].x;
}
Flow++;
}
void sap(){
for (int i=0;i<=p;i++){
cur[i]=ls[i];
d[i]=0;
num[i]=0;
}
num[0]=p+1;
int i=S;
while (d[S]
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
cur[i]=g[cur[i]].next;
}
if (cur[i]==0){
num[d[i]]–;
if (num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=S) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==T){
change();
i=S;
}
}
}
}
bool Try(int k){
p++;
add(S,p,1);
p++;
add(p,T,1);
for (int i=1;i
add(i<<1,p,1);
sap();
if (k-Flow<=n) return true;
return false;
}
int main(){
freopen("ball10.in","r",stdin);
freopen("ball10.ans","w",stdout);
cin >> n;
for (int i=1;i<=99999;i++)
if (!Try(i)){
cout << i-1 << endl;
return 0;
}
}
线性规划与网络流之3 最小路径覆盖
题目：http://www.byvoid.com/blog/lpf24-solution/
分析：
求一个有向无环图的最小路径覆盖。
构造二分图，每个点拆成两个。然后按边的关系从左边向右边连边即可。
然后求最大匹配。最后输出N-最大匹配数即可。
HINT
另外也可以求无向图的最小路径覆盖。
最后答案就是N-最大匹配数/2
code:
#include
#define N 10000
int n,e,x[E],y[E],next[E],ls[N],link[N],v[N];
void add(int X,int Y,int i){
x[i]=X; y[i]=Y; next[i]=ls[X]; ls[X]=i;
}
void init(){
scanf("%d%d",&n,&e);
int X,Y;
for (int i=1;i<=e;i++){
scanf("%d%d",&X,&Y);
add(X,Y,i);
}
}
bool find(int k,int mark){
for (int t=ls[k];t!=0;t=next[t])
if (v[y[t]]!=mark){
int q=link[y[t]];
link[y[t]]=k;
v[y[t]]=mark;
if (q==0 || find(q,mark)) return true;
link[y[t]]=q;
}
return false;
}
void match(){
memset(link,0,sizeof(link));
memset(v,0,sizeof(v));
int MatchNum=0;
for (int i=1;i<=n;i++)
if (find(i,i)) MatchNum++;
printf("%dn",n-MatchNum);
}
int main(){
freopen("path.in","r",stdin);
freopen("path.ans","w",stdout);
init();
match();
return 0;
}
线性规划与网络流之2 最大权闭合图
题目：http://www.byvoid.com/blog/lpf24-solution/
分析
按照题意，可以构建一个二分图，然后我们可以发现这是一个依赖关系的最大权取值问题。所以直接套用《最小割模型在信息学竞赛中的应用》里的最大权闭合图模型解决。
code:
#include
#define N 1001
#define Maxnum 1000000000
int m,n,x[E],y[E],next[E],c[E],op[E],ls[N],d[N],fa[N],num[N],cur[N],vs,vt,e=0,s=0,flow=0;
void add(int X,int Y,int C){
e++;
x[e]=X; y[e]=Y; c[e]=C; next[e]=ls[X]; ls[X]=e; op[e]=e+1;
e++;
x[e]=Y; y[e]=X; c[e]=0; next[e]=ls[Y]; ls[Y]=e; op[e]=e-1;
}
void init(){
scanf("%d%d",&m,&n);
vs=0; vt=m+n+1;
char ch;
for (int i=1;i<=m;i++){
int t;
scanf("%d",&t);
s+=t;
add(vs,i,t);
while (scanf("%c",&ch)!=EOF && ch!=’n’){
scanf("%d",&t);
add(i,m+t,Maxnum);
}
}
for (int i=1;i<=n;i++){
int t;
scanf("%d",&t);
add(m+i,vt,t);
}
}
void relabel(int k){
int min=vt,i=ls[k];
cur[k]=ls[k];
while (i>0){
if (c[i]>0 && d[y[i]]
}
d[k]=min+1;
}
void change(){
int i=vt,nf=Maxnum;
while (i!=vs){
if (c[fa[i]]
}
flow+=nf;
i=vt;
while (i!=vs){
c[fa[i]]-=nf;
c[op[fa[i]]]+=nf;
i=x[fa[i]];
}
}
void sap(){
for (int i=vs;i<=vt;i++){
num[i]=0;
d[i]=0;
cur[i]=ls[i];
}
num[0]=vt+1;
int i=vs;
while (d[vs]
if (d[x[cur[i]]]==d[y[cur[i]]]+1 && c[cur[i]]>0)
break;
else
cur[i]=next[cur[i]];
if (cur[i]==0){
num[d[i]]–;
if (num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=vs) i=x[fa[i]];
}
else{
fa[y[cur[i]]]=cur[i];
i=y[cur[i]];
if (i==vt){
change();
i=vs;
}
}
}
}
int main(){
freopen("shut10.in","r",stdin);
freopen("shut10.ans","w",stdout);
init();
sap();
printf("%dn",s-flow);
}