8 条题解
-
1
Sky1231 (sky1231) LV 10 @ 2017-06-06 12:06:55
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; int n,m,x_n,y_n,b; vector<int> l; vector<vector<int> > p_x; vector<vector<int> > p_y; vector<bool> c; vector<vector<bool> > x_y_r; vector<vector<char> > a; void c_v_1() { l.resize(0); p_x.resize(0); p_y.resize(0); x_y_r.resize(0); a.resize(0); } int find_1(int now) { for (int i=1;i<=y_n;i++) if (x_y_r[now][i]==1&&c[i]==0) { int temp=l[i]; l[i]=now,c[i]=1; if (temp>0) { if (find_1(temp)==1) return 1; } else return 1; l[i]=temp; } return 0; } int work_1() { int ans=0; for (int i=1;i<=x_n;i++) { c.resize(0); c.resize(y_n+1,0); ans+=find_1(i); } return ans; } int main() { while (~scanf("%d%d",&n,&m)) { a.resize(n+1); p_x.resize(n+1); p_y.resize(n+1); for (int i=1;i<=n;i++) { a[i].resize(m+1,0); p_x[i].resize(m+1,0); p_y[i].resize(m+1,0); char temp; scanf("%c",&temp); for (int j=1;j<=m;j++) scanf("%c",&a[i][j]); } x_n=b=1; for (int i=1;i<=n;i++,x_n+=(b==0)?(b=1):0) for (int j=1;j<=m;j++) if (a[i][j]=='E') p_x[i][j]=x_n,b=0; else if (a[i][j]=='W'&&b==0) x_n++,b=1; x_n-=b; y_n=b=1; for (int i=1;i<=m;i++,y_n+=(b==0)?(b=1):0) for (int j=1;j<=n;j++) if (a[j][i]=='E') p_y[j][i]=y_n,b=0; else if (a[j][i]=='W'&&b==0) y_n++,b=1; y_n-=b; x_y_r.resize(x_n+1); for (int i=1;i<=x_n;i++) x_y_r[i].resize(y_n+1,0); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (p_x[i][j]>0&&p_y[i][j]>0) x_y_r[p_x[i][j]][p_y[i][j]]=1; l.resize(y_n+1,0); printf("%d\n",work_1()); } }-
很H2O的题
-
-
0
Silence•轩辕•寂 LV 10 @ 2014-04-19 13:00:30
过了这题，AC率提高了一个百分点！水过。。。
-
0
最大流写渣了。。。
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 724 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 724 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1120 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1196 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1308 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 1520 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1524 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 1516 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1520 KiB, score = 10
Accepted, time = 200 ms, mem = 1524 KiB, score = 100首先对每行每列各自单独处理，对联通块进行染色，然后设点i,j在行的颜色是wi，在列的颜色是vi，对于一个wi，连边(S,Wi,1)，对于一个vi连(vi,T,1),若i,j是空白，则连边(wi,vi,1)，最大流即为答案：
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std ;
#define MAXN 110
#define inf 0x7fffffff
#define MAXV 10010struct network {
struct edge {
edge *next , *pair ;
int t , f ;
} *head[ MAXV ] ;network( ) {
memset( head , 0 , sizeof( head ) ) ;
}void Add( int s , int t , int f ) {
edge *p = new( edge ) ;
p -> t = t , p -> f = f , p -> next = head[ s ] ;
head[ s ] = p ;
}void AddEdge( int s , int t , int f ) {
Add( s , t , f ) , Add( t , s , 0 ) ;
head[ s ] -> pair = head[ t ] , head[ t ] -> pair = head[ s ] ;
}int h[ MAXV ] , gap[ MAXV ] , S , T ;
edge *d[ MAXV ] ;int sap( int v , int flow ) {
if ( v == T ) return flow ;
int rec = 0 ;
for ( edge *p = d[ v ] ; p ; p = p -> next ) if ( p -> f && h[ v ] == h[ p -> t ] + 1 ) {
int ret = sap( p -> t , min( flow - rec , p -> f ) ) ;
p -> f -= ret , p -> pair -> f += ret , d[ v ] = p ;
if ( ( rec += ret ) == flow ) return flow ;
}
if ( ! ( -- gap[ h[ v ] ] ) ) h[ S ] = T ;
gap[ ++ h[ v ] ] ++ , d[ v ] = head[ v ] ;
return rec ;
}int maxflow( ) {
int rec = 0 ;
for ( int i = 0 ; i ++ < T ; ) h[ i ] = gap[ i ] = 0 , d[ i ] = head[ i ] ;
gap[ S ] = T ;
while ( h[ S ] < T ) rec += sap( S , inf ) ;
return rec ;
}} net ;
int node[ MAXN ][ MAXN ][ 2 ] , n , m , V = 0 ;
char s[ MAXN ][ MAXN ] ;int main( ) {
scanf( "%d%d" , &n , &m ) ;
for ( int i = 0 ; i ++ < n ; ) scanf( "%s" , s[ i ] + 1 ) ;
for ( int i = 0 ; i ++ < n ; ) {
for ( int j = 0 ; j ++ < m ; ) {
if ( j == 1 || s[ i ][ j ] == 'W' ) V ++ ;
node[ i ][ j ][ 0 ] = V ;
}
}
for ( int i = 0 ; i ++ < m ; ) {
for ( int j = 0 ; j ++ < n ; ) {
if ( j == 1 || s[ j ][ i ] == 'W' ) V ++ ;
node[ j ][ i ][ 1 ] = V ;
}
}
net.S = ++ V ; net.T = ++ V ;
for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < m ; ) {
if ( j == 1 || node[ i ][ j ][ 0 ] != node[ i ][ j - 1 ][ 0 ] ) {
net.AddEdge( net.S , node[ i ][ j ][ 0 ] , 1 ) ;
}
if ( i == 1 || node[ i ][ j ][ 1 ] != node[ i - 1 ][ j ][ 1 ] ) {
net.AddEdge( node[ i ][ j ][ 1 ] , net.T , 1 ) ;
}
if ( s[ i ][ j ] == 'E' ) net.AddEdge( node[ i ][ j ][ 0 ] , node[ i ][ j ][ 1 ] , 1 ) ;
}
printf( "%d\n" , net.maxflow( ) ) ;
return 0 ;
} -
0
VijosNT Mini 2.0.5.6
#01: Accepted (85ms, 25256KB)
#02: Accepted (97ms, 25256KB)
#03: Accepted (105ms, 25256KB)
#04: Accepted (101ms, 25256KB)
#05: Accepted (101ms, 25256KB)
#06: Accepted (82ms, 25256KB)
#07: Accepted (113ms, 25256KB)
#08: Accepted (93ms, 25256KB)
#09: Accepted (97ms, 25256KB)
#10: Accepted (78ms, 25256KB)
Accepted / 100 / 957ms / 25256KB
二分图匹配
将每个点拆掉，将x坐标，y坐标建立两个集合，进行匹配
如图：
EEEEWWEEE
则前4个点的x坐标缩成一个点，后面的三个点的x坐标缩成一个点
y坐标同理。
之后对原先图上的每个点的的新xy坐标连接
如:
1 2 3
1 E E W
2 W E E
p[1][1].x=p[1][2].x=1
p[1][1].y=1 p[1][2].y=p[2][2].y=2 p[2][3].y=3
新图 m[p[i][j].x][p[i][j].y]=1;
之后对新图进行匈牙利就行了。 -
0
prince_hao LV 10 @ 2010-07-28 12:12:51
原来真的是匹配，比赛的时候觉得匹配负荷太大，写了搜索。
用邻接表就好了，其实分析一下本题的性质，NM不会非常大的- -
原来找交叉的时候没排除草坪也能拿60。
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
LV 0 @ 2010-07-27 16:28:58
建模+二分图匹配
建模：一个左图的点包括至少一个空地以及这个空地横向能影响到的空地和草地。
一个右图的点包括至少一个空地以及这个空地竖向能影响到的空地和草地。
这样得到的每个点包括的空地最多只能取一个。
这样的两个点（一个在左图，一个在右图）有边的条件是有公共的空地。
这样会建立一个二分图，每条边对应的是一个空地，有些边会交在某个结点，说明这些边对应的空地是冲突的，只能选一个。
这样求选最多的空地，正好符合二分图最大匹配。
建模后，用Hungary在建好的图中做一遍二分图最大匹配。编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
Sky1231 (sky1231)
LV 10
@ 2017-06-06 12:06:55
- 1
