【题目大意】求每一段F[I]的最大值。
【算法分析】直接暴力打表。
【CODE】
#include
分类存档：默认分类
[POJ 1192] 树形动态规划
[POJ 3683] 2-SAT、输出方案
【题目大意】给定N个区间（A，B），和长度len，让你对于每一组区间在(A,A+len)和(B-len,B)这两个区间中选一个，使得选取的区间交集为空集
【算法分析】典型的2-SAT，要注意一下输出方案必须按反拓扑序输出。
【其它】贡献2WA。del过程一开始没写好，应先把图倒置。
【CODE】
#include
[SGU 212]层次图的网络流、预流推进+sap**
【题目大意】 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
#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].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].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]
}
void change(){
int nf=inf;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c
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]
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;i
}
int main(){
init();
first_push();
prebfs();
sap();
print();
}
[SGU 210]最大匹配、贪心**
【题目大意】 N个男的、N个女的（N<=400），互相匹配。每个男的有权值，求最后权值最大。
【算法分析】将男的按权值排序，然后根据这个顺序来最大匹配。匈牙利算法每次寻找交错轨的话，前面已匹配的节点绝不会再丢失匹配，所以根据这个性质，可以这么做。
【其它】SGU跑了近10分钟给了我一个CE。。。#include
【CODE】
#include
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;i
}