作者存档：edward_mj

【题目大意】给定N个区间（A，B），和长度len，让你对于每一组区间在(A,A+len)和(B-len,B)这两个区间中选一个，使得选取的区间交集为空集

【算法分析】典型的2-SAT，要注意一下输出方案必须按反拓扑序输出。

【其它】贡献2WA。del过程一开始没写好，应先把图倒置。

【CODE】

#include

【题目大意】 N个点M条边，每个点的距离标号已给出，且I阶段的点只向I+1阶段的点连边，求最大流。

【算法分析】本来以为是直接sap秒杀。。。因为见惯了这sap的暴力。。。但是做了这题以后，我终于知道了一件事，sap不是万能的，没有sap却是万万不能的。。。
这个比较囧。一开始以为水题，直接sap，10分钟交上去，TLE AT 17
然后就各种囧，加了个优化，就是预处理sap的d数组，依然飘逸地TLE
然后我就是开始想HLPP，但是用不习惯，不爽。。。
然后我就想，能不能把sap和预流推进搞到一起去呢？
于是就诞生了今天我写的这个东东。。。
下面进入正题：
其实说来也简单，因为是层次图，所以我就先从S点开始bfs地向后推进一次，然后在根据上一次bfs的list把上一次推进不能到达T的盈余推回到S来，然后就可以初始了一个流出来
最后再用bfs预处理sap的标号，最后用我们可爱的sap把它解决了。。。

【其它】重写以后1A
994533 02.02.10 17:37 edward 212 .CPP Accepted 1412 ms 15643 kb 这个比较激动。。。看着比较少人A，加上经历了艰难困苦以后终于AC，yeah一个
【CODE】
#include #include #include #define N 1555
#define E 666666
//#define N 100
//#define E 200
#define inf 0x7FFFFFFF
struct gtp{int x,y,next,op,c;}g[E];
int n,edge,L,S,T;
int e[N],fa[N],ls[N],cur[N],d[N],num[N],list[N],C[E],v[N];

inline void addedge(int x,int y,int c){
edge++;
g[edge].x=x; g[edge].y=y; g[edge].c=c; g[edge].op=edge+1;
g[edge].next=ls[x]; ls[x]=edge;
edge++;
g[edge].x=y; g[edge].y=x; g[edge].c=0; g[edge].op=edge-1;
g[edge].next=ls[y]; ls[y]=edge;
}   

void init(){
int m,x,y,c;
scanf("%d%d%d",&n,&m,&L);
for (int i=1;i<=n;i++){
scanf("%d",&x);
if (x==1) S=i;
if (x==L) T=i;
}   
for (int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&c);
addedge(x,y,c);
C[edge]=c;
C[edge-1]=c;
}   
}

void first_push(){
list[1]=S; e[S]=inf; v[S]=1;
int head=0,tail=1,nf;
while (head!=tail){
head++;
for (int t=ls[list[head]];t;t=g[t].next)
if ((t&1) && g[t].c){
nf=g[t].c; if (e[list[head]]e[g[t].x]-=nf;
e[g[t].y]+=nf;
g[t].c-=nf;
if (nf && !v[g[t].y]){
tail++;
list[tail]=g[t].y;
v[g[t].y]=1;
}   
}   
}
// push back
for (int i=tail-1;i>=1;i–){
for (int t=ls[list[i]];t;t=g[t].next)
if (!(t&1) && (C[g[t].op]-g[g[t].op].c)){
nf=C[g[t].op]-g[g[t].op].c; if (e[list[i]]e[g[t].x]-=nf;
e[g[t].y]+=nf;
g[g[t].op].c+=nf;
}   
}   
}

void prebfs(){
for (int i=1;i<=n;i++) d[i]=inf;
list[1]=T; d[T]=0;
int head=0,tail=1;
while (head!=tail){
head++;
for (int t=ls[list[head]];t;t=g[t].next)
if (!(t&1) && g[g[t].op].c && d[g[t].y]==inf){
d[g[t].y]=d[g[t].x]+1;
tail++;
list[tail]=g[t].y;
}
}   
}

void relabel(int k){
int mm=n;
cur[k]=ls[k];
for (int t=ls[k];t;t=g[t].next)
if (g[t].c && d[g[t].y]d[k]=mm+1;
}

void change(){
int nf=inf;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].cfor (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}   
}       

void sap(){
for (int i=1;i<=n;i++){
num[d[i]]++;
cur[i]=ls[i];
}   
int i=S;
while (d[S]for (;cur[i];cur[i]=g[cur[i]].next)
if (g[cur[i]].c && d[g[cur[i]].y]+1==d[i]) break;
if (!cur[i]){
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 print(){
for (int i=1;iprintf("%dn",C[i]-g[i].c);
}   

int main(){
init();
first_push();
prebfs();
sap();
print();
}   

【题目大意】 N个男的、N个女的（N<=400），互相匹配。每个男的有权值，求最后权值最大。 【算法分析】将男的按权值排序，然后根据这个顺序来最大匹配。匈牙利算法每次寻找交错轨的话，前面已匹配的节点绝不会再丢失匹配，所以根据这个性质，可以这么做。 【其它】SGU跑了近10分钟给了我一个CE。。。#include 994478 02.02.10 16:06 edward 210 .CPP Accepted 559 ms 2499 kb
【CODE】
#include #include #include #include using namespace std;
struct edge{int y; edge *next;};
struct data{int w,mark;}d[411];
int n,link[411],cover[411],ans[411];
edge *ls[411];
bool cmp(data x,data y){return x.w>y.w;}

void add(int x,int y){
edge *p=new edge;
p->y=y; p->next=ls[x]; ls[x]=p;
}

bool dfs(int k){
for (edge *t=ls[k];t;t=t->next)
if (!cover[t->y]){
cover[t->y]=1;
int q=link[t->y];
link[t->y]=k;
if (q==0 || dfs(q)) return true;
link[t->y]=q;
}   
return false;
}   

int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
ls[i]=NULL;
scanf("%d",&d[i].w);
d[i].mark=i;
}
for (int i=1;i<=n;i++){
int num,x;
scanf("%d",&num);
for (int j=1;j<=num;j++){
scanf("%d",&x);
add(i,x);
}   
}   
sort(&d[1],&d[n+1],cmp);
for (int now=1;now<=n;now++){
memset(cover,0,sizeof(cover));
dfs(d[now].mark);
}
for (int i=1;i<=n;i++)
if (link[i]) ans[link[i]]=i;
for (int i=1;iprintf("%dn",ans[n]);
}   

【题目大意】 有n个人下棋，每次有两个人下，赢者留下再比(可以与刚下败的人)。给出每个人下的次数，要求出一种可行方案，输出每次比赛的过程，赢者放在第一列，败者放在第二列。

【算法分析】传说中的构造。。。看了别人的还不懂，然后再看了程序才懂= =
就是把那些人按出场的次数从大到小排序，然后让前面的人尽量赢，然后再按顺序填掉剩下的表就行了。
我看的是这个：http://www.cppblog.com/schindlerlee/archive/2010/01/27/106503.html?opt=admin
但是值得注意的是最后他说的那句剩下的随便填是绝对不行的，因为之前我写过一种方法。。。随便填最后会到自己打自己。应该是按照升序来填，这样就会尽量避免和自己打。

【其它】
994465 02.02.10 15:31 edward 138 .CPP Accepted 25 ms 827 kb
【CODE】
#include #include #include #include using namespace std;
struct datat{int d,mark;}a[111];
int n,ans[111111][2];

bool cmp(datat x,datat y){return x.d>y.d;}

int main(){
int sum=0;
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a[i].d);
a[i].mark=i;
sum+=a[i].d;
}
sort(&a[1],&a[n+1],cmp);
sum/=2;
printf("%dn",sum);
int tot=0;
for (int i=1;i<=n;i++){
while (tota[i].d–;
tot++;
ans[tot][0]=a[i].mark;
}   
if (tottot++;
ans[tot][1]=a[i].mark;
ans[tot][0]=a[i+1].mark;
a[i+1].d–;
a[i].d–;
}   
}
int top=1;
while (a[top].d==0) top++;
for (int i=1;i<=sum;i++){
printf("%d ",ans[i][0]);
if (ans[i][1]) printf("%d",ans[i][1]);
else{
printf("%d",a[top].mark);
a[top].d–;
while (a[top].d==0) top++;
}  
printf("n");
}
}   

【题目大意】 数轴上有N个区间，每个区间有一个权值C，你可以选择任意多的区间，但是数轴上某一段不能被覆盖超过K次，求最大能获得的权值。

【算法分析】这个连边感觉比较巧，不过挺容易理解。
就是先离散化，然后i向i+1连边，容量为limit，费用为0
然后再对于每个区间连边a[i]->b[i]，容量为1，费用为w[i]
新增源汇，连边[S,1]，容量为limit，费用为0
连边[n,T]，容量为limit，费用为0
实际到达每一个点的话就相当于选择是否分配流到以这个点位起点的区间边上，然后再向后流去。
做一次最大费用最大流即可。

【其它】1A
6401617 edward2 3680 Accepted 644K 407MS G++ 2404B 2010-02-02 18:50:17
【CODE】
#include #include #include #include using namespace std;
#define N 1000
struct gtp{int x,y,next,w,c,op;}g[10000];
int n,e,m,limit,cost;
int a[N],b[N],w[N],zb[N];
int ls[N],fa[N],d[N],v[N],list[N];

void init(){
scanf("%d%d",&m,&limit);
for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&w[i]);
}

void lisan(){
int tail=0;
for (int i=1;i<=m;i++){
zb[++tail]=a[i];
zb[++tail]=b[i];
}
sort(&zb[1],&zb[tail+1]);
n=0;
for (int i=1;i<=tail;i++)
if (n==0 || zb[n]!=zb[i]) zb[++n]=zb[i];
}

void add(int x,int y,int c,int w){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w;
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].w=-w;
g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}

int find(int x){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (x>zb[mid]) l=mid+1;
else r=mid;
}
return l;
}

void build(){
e=0; memset(ls,0,sizeof(ls));
for (int i=0;i<=n;i++) add(i,i+1,limit,0);
for (int i=1;i<=m;i++)
add(find(a[i]),find(b[i]),1,w[i]);
}

bool spfa(){
for (int i=0;i<=n+1;i++){
d[i]=-1;
v[i]=0;
}
d[0]=0; v[0]=1; list[0]=0;
int head=-1,tail=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t;t=g[t].next)
if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
d[g[t].y]=d[g[t].x]+g[t].w;
fa[g[t].y]=t;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}
}
v[list[head]]=0;
}
if (d[n+1]==-1) return false;
return true;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=n+1;i!=0;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=n+1;i!=0;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
cost+=nf*d[n+1];
}

void mincost_maxflow(){
cost=0;
while (spfa()) change();
}

int main(){
int tc;
scanf("%d",&tc);
for (int i=0;i init();
lisan();
build();
mincost_maxflow();
printf("%dn",cost);
}
}