发表于 
1
2
3
4
5
6
7
8
9
第一问lis
第二问和第三问都是网络流
第二问的建图：
s - 1 - i (f[i]==1)
i - 1 - i'
i' - 1 - j (f[i]+1==f[j]&&a[i]<=a[j]&&i<j)
i' - 1 - t (f[i]==ans)
第三问只要把(s,1),(1,1'),(n,n'),(n',t)的流量改成INF
82分的原因是加边的时候忘记判a[i]>=a[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=508;
int n,s,t,tmp;
int a[N];
int f[N],lis[N],num;
int ans;
int nume=1,head[N*2],cur[N*2];
struct node{
    int to,nxt,f;
}e[N*N*2];
inline void addedge(int x,int y,int z){
    e[++nume]=(node){y,head[x],z};head[x]=nume;
    e[++nume]=(node){x,head[y],0};head[y]=nume;
}
int dis[N*2];
int q[N*2],he,ta;
inline bool bfs()
{
    memset(dis,0,sizeof(dis));
    he=1;ta=2;
    q[1]=s;
    dis[s]=1;
    while(he!=ta){
        int x=q[he];
        ++he;
        for(int i=head[x];i;i=e[i].nxt){
            if(e[i].f&&!dis[e[i].to]){
                dis[e[i].to]=dis[x]+1;
                if(e[i].to==t)	return 1;
                q[ta]=e[i].to;
                ++ta;
            }
        }
    }
    return 0;
}
inline int dfs(int x,int low)
{
    if(x==t||!low)	return low;
    int flow=0,tmp;
    for(int i=head[x];i;i=e[i].nxt){
        if(dis[e[i].to]==dis[x]+1&&(tmp=dfs(e[i].to,min(low,e[i].f)))){
            flow+=tmp;
            low-=tmp;
            e[i].f-=tmp;
            e[i^1].f+=tmp;
            if(!low)	return flow;	
        }
    }
    if(low)	dis[x]=0;
    return flow;
}
inline int dinic()
{
    int maxflow=0;
    while(bfs()){
        for(int i=0;i<=t;++i){
            cur[i]=head[i];
        }
        maxflow+=dfs(s,INT_MAX);
    }
    return maxflow;
}
inline void init()
{
    for(int i=0;i<=t;++i){
        for(int j=head[i];j;j=e[j].nxt){
            if(j%2==0){
                if((i==0&&e[j].to==1) || (i==1&&e[j].to==1+n) || (i==n&&e[j].to==n+n) || (i==n+n&&e[j].to==t)){
                    e[j].f=INT_MAX;
                    e[j^1].f=0;
                }
                else{
                    e[j].f+=e[j^1].f;
                    e[j^1].f=0;
                }
            }
        }
    }
}
int main()
{
    n=read();
    s=0;t=n+n+1;
    for(int i=1;i<=n;++i){
        a[i]=read();
    }
    
    for(int i=1;i<=n;++i){
        if(a[i]>=lis[num]){
            lis[++num]=a[i];
            f[i]=num;
        }
        else{
            tmp=upper_bound(lis+1,lis+num+1,a[i])-lis;
            lis[tmp]=a[i];
            f[i]=tmp;
        }
    }
    for(int i=1;i<=n;++i){
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;++i){
        addedge(i,i+n,1); 
        if(f[i]==1)	addedge(s,i,1);
        if(f[i]==ans)	addedge(i+n,t,1);
        for(int j=1;j<i;++j){
            if(f[i]==f[j]+1&&a[i]>=a[j]){
                addedge(j+n,i,1);
            }
        }
    }
    printf("%d\n",dinic());
    init();
    printf("%d\n",dinic());
    return 0;
}

发表于 
1
2
3
4
5
6
7
对最小割还是不熟
答案为所有的值减去掉的最小值。
去掉的原因是相邻格子不能同时取。
黑白染色，也就是要么不取黑，要么不取白
相邻的连边 s - black's key - black - INF - white - white's key - t
那最小割就是去掉的最小值
64分的错误原因是用u的奇偶性判断黑白了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=108;
int n,m,u,v,s,t;
int a[N][N];
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0},tx,ty;
LL ans;
inline int getid(int x,int y)
{
	return (x-1)*m+y;
}
int nume=1,head[N*N],cur[N*N];
struct node{
	int to,nxt,f;
}e[N*N*4];
inline void addedge(int x,int y,int z)
{
	e[++nume]=(node){y,head[x],z};head[x]=nume;
	e[++nume]=(node){x,head[y],0};head[y]=nume;
}
int dis[N*N];
int q[N*N],he,ta;
inline bool bfs()
{
	memset(dis,0,sizeof(dis));
	he=1;ta=2;
	q[1]=s;
	dis[s]=1;
	while(he!=ta){
		int x=q[he];
		++he;
		for(int i=head[x];i;i=e[i].nxt){
			if(e[i].f&&!dis[e[i].to]){
				dis[e[i].to]=dis[x]+1;
				if(e[i].to==t)	return 1;
				q[ta]=e[i].to;
				++ta; 
			}
		}
	}
	return 0;
}
inline int dfs(int x,int low)
{
	if(x==t||!low)	return low;
	int flow=0,tmp;
	for(int &i=cur[x];i;i=e[i].nxt){
		if(dis[e[i].to]==dis[x]+1&&(tmp=dfs(e[i].to,min(low,e[i].f)))){
			flow+=tmp;
			low-=tmp;
			e[i].f-=tmp;
			e[i^1].f+=tmp;
			if(!low)	return flow;
		}
	}
	if(low)	dis[x]=0;
	return flow;
} 
inline LL dinic()
{
	LL maxflow=0;
	while(bfs()){
		for(int i=0;i<=t;++i){
			cur[i]=head[i];
		}
		maxflow+=dfs(s,INT_MAX);
	}
	return maxflow;
}
int main()
{
	n=read();m=read();
	s=0;t=n*m+1;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			a[i][j]=read();
			ans+=a[i][j];
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			u=getid(i,j);
			if((i+j)%2==0){
				addedge(s,u,a[i][j]);
				for(int k=0;k<4;++k){
					tx=i+dx[k];
					ty=j+dy[k];
					if(tx<1||tx>n||ty<1||ty>m)	continue;
					v=getid(tx,ty);
					addedge(u,v,INT_MAX);
				}
			}
			else{
				addedge(u,t,a[i][j]);
			}
		}
	}
	printf("%lld",ans-dinic());
	return 0;
}

发表于 
1
基础网络流，不要打错变量名！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int K=28,N=1008;
int n,m,k,p,tmp;
int s,t;
int req[K];
int ans;
int nume=1,head[N+K],cur[N+K];
struct node{
    int to,nxt,f;
}e[N*K*2];
inline void addedge(int x,int y,int z)
{
    e[++nume]=(node){y,head[x],z};head[x]=nume;
    e[++nume]=(node){x,head[y],0};head[y]=nume;
}
int dis[N+K];
int he,ta,q[N+K];
inline bool bfs()
{
    memset(dis,0,sizeof(dis));
    he=1;ta=2;
    q[1]=s;
    dis[s]=1;
    while(he!=ta){
        int x=q[he];
        ++he;
        for(int i=head[x];i;i=e[i].nxt){
            if(e[i].f&&!dis[e[i].to]){
                dis[e[i].to]=dis[x]+1;
                if(e[i].to==t)	return 1;
                q[ta]=e[i].to;
                ++ta;
            }
        }
    }
    return 0;
}
inline int dfs(int x,int low)
{
    if(x==t||!low)	return low;
    int flow=0,tmp;
    for(int &i=cur[x];i;i=e[i].nxt){
        if(dis[e[i].to]==dis[x]+1&&(tmp=dfs(e[i].to,min(low,e[i].f)))){
            flow+=tmp;
            low-=tmp;
            e[i].f-=tmp;
            e[i^1].f+=tmp;
            if(!low)	return flow;
        }
    }
    if(low)	dis[x]=0;
    return flow;
}
inline int dinic()
{
    int maxflow=0;
    while(bfs()){
        for(int i=0;i<=t;++i){
            cur[i]=head[i];
        }
        maxflow+=dfs(s,INT_MAX);
    }
    return maxflow;
}
vector<int> plan[K];
inline void print()
{
    for(int i=1;i<=n;++i){
        for(int j=head[i];j;j=e[j].nxt){
            if(j%2==0&&e[j].f==0){//i/j
                plan[e[j].to-n].pb(i);//i/j
                break;
            }
        }
    }
    for(int i=1;i<=k;++i){
        printf("%d:",i);
        for(int j=0;j<plan[i].size();++j){
            printf(" %d",plan[i][j]);
        }
        puts("");
    }
}
int main()
{
    k=read();n=read();
    s=0;t=n+k+1;
    for(int i=1;i<=k;++i){
        req[i]=read();
        addedge(i+n,t,req[i]);
        m+=req[i];
    }
    for(int i=1;i<=n;++i){
        addedge(s,i,1);
        p=read();
        for(int j=1;j<=p;++j){
            tmp=read();
            addedge(i,tmp+n,1);
        }
    }
    ans=dinic();
    if(ans!=m){
        puts("No Solution!");
    }
    else{
        print();
    }
    return 0;
}

发表于 
1
2
3
4
5
正确的做法是网络流
若i+j为平方数(i<j), i - 1 - j
转化成最小路径覆盖
当最小路径覆盖>n时，前一个为答案
记得在上一次的残余网络里跑，不用清空流量
阅读全文 »

发表于

题意：

891C. Envy
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

For a connected undirected weighted graph $G$, MST (minimum spanning tree) is a subgraph of $G$ that contains all of $G$’s vertices, is a tree, and sum of its edges is minimum possible.

You are given a graph $G$. If you run a MST algorithm on graph it would give you only one MST and it causes other edges to become jealous. You are given some queries, each query contains a set of edges of graph $G$, and you should determine whether there is a MST containing all these edges or not.

阅读全文 »

发表于

题意：

小M在玩一个游戏。游戏有N轮，每一轮，系统给出两个数X和Y，她的任务是将当前得到的所有X和Y两两配对，将每对X、Y求和，使得最大的和最小。
小M算晕了，于是找你帮忙~

阅读全文 »

发表于

题目：

定义：一个 P 单词是指，这个单词不包含 3 个连续的辅音字母，且不包含 3 个连续的元音字母，且至少包含一个字母 L。
现有一个由大写字母与下划线构成的单词，要求将所有下划线替换成大写字母，构成一个新的单词，求构成 P 单词的方案数。
元音字母是指 A，E，I，O，U，其余字母都是辅音字。

阅读全文 »

发表于

题意：

农民约翰已经收到了一批有N个的大型干草包（1<=N<=100,000），并放置在沿着通往他的谷仓的路不同位置。不幸的是，他完全忘记了Bessie牛是放牧的路上，她现在可能被困在那些干草包中！每个干草包J都有一个大小S[J]和一个位置P[J]，提供那个干草包在那个一维道路的位置。贝茜奶牛可以在路上自由走动，甚至到这个干草包所在的位置，但她无法穿越这个位置。作为一个例外，如果她在同一个方向跑D个速度单位，她就可以有足够的速度突破，并永久消除任何干草包，只要那个干草包大小严格小于D。当然，在这之后，她会打开更大的空间让她跑向别的干草包，并消除它们。
如果她能突破最左边或最右边的干草包，则贝茜可以逃掉。请计算由实数的起始位置组成的道路最小需要多长，使Bessie不能逃脱。

阅读全文 »