| 取数游戏（TPM） |
| 难度级别：D； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
给你一个n*n的格子的棋盘，每个格子里面有一个非负数。从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能有公共边，并且取出的数的和最大。（二分图匹配练习） |
输入 |
第一行是一个正整数n (n<20)。 接下来是 n*n 个非负数。 |
输出 |
输出可能取得的最大的和。 |
输入示例 |
3 5 9 4 8 3 6 2 7 1 |
输出示例 |
30 |
其他说明 |
n<20 |
题解：“没有公共边”这是赤裸裸的二分图呀！随便按(i+j)&1造个二分图跑了就行。。。
而且，这是我第一个接触的构造题吧= = 还是非常有纪念意义的= =我记得当年还是小健建给我亲自敲了一遍DInic然后敲了一遍这道题。。。回忆满满呢~
现在老练的ISAP+缩行：
//这两道题有什么区别。。。= =
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=+,maxm=+,inf=-1u>>;
struct ISAP{
struct tedge{int x,y,w,next;}adj[maxm];int ms,fch[maxn];
int d[maxn],s[maxn],cur[maxn],gap[maxn],n,top;
void init(int n){
this->n=n;ms=;top=;
memset(d,-,sizeof(d));
memset(fch,-,sizeof(fch));
return;
}
void addedge(int u,int v,int w){
adj[ms]=(tedge){u,v,w,fch[u]};fch[u]=ms++;
adj[ms]=(tedge){v,u,,fch[v]};fch[v]=ms++;
return;
}
void bfs(){
queue<int>Q;Q.push(n);d[n]=;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=fch[u];i!=-;i=adj[i].next){
int v=adj[i].y;
if(d[v]==-) d[v]=d[u]+,Q.push(v);
}
} return;
}
int maxflow(int S,int T){
n=T;bfs();int k=S,i,flow=;
for(i=;i<=n;i++) cur[i]=fch[i],gap[d[i]]++;
while(d[S]<n){
if(k==n){
int mi=inf,pos;
for(i=;i<top;i++) if(adj[s[i]].w<mi) mi=adj[s[i]].w,pos=i;
for(i=;i<top;i++) adj[s[i]].w-=mi,adj[s[i]^].w+=mi;
flow+=mi;top=pos;k=adj[s[top]].x;
}
for(i=cur[k];i!=-;i=adj[i].next){
int v=adj[i].y;
if(adj[i].w&&d[k]==d[v]+){cur[k]=i;k=v;s[top++]=i;break;}
}
if(i==-){
int lim=n;
for(i=fch[k];i!=-;i=adj[i].next){
int v=adj[i].y;
if(adj[i].w&&d[v]<lim) lim=d[v],cur[k]=i;
} if(--gap[d[k]]==) break;
d[k]=lim+;gap[d[k]]++;
if(k!=S) k=adj[s[--top]].x;
}
} return flow;
}
}sol;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
int A[][],mx[]={,-,,},my[]={,,-,};
void init(){
int n=read();long long ans=;
sol.init(n*n+);int S=n*n+,T=n*n+;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
A[i][j]=read();
if((i+j)&){
sol.addedge(S,i*n+j-n,A[i][j]);
for(int d=;d<;d++){
int nx=i+mx[d],ny=j+my[d];
if(nx>=&&nx<=n&&ny>=&&ny<=n) sol.addedge(i*n+j-n,nx*n+ny-n,inf);
}
}
else sol.addedge(i*n+j-n,T,A[i][j]);
ans+=A[i][j];
}
write(ans-sol.maxflow(S,T));
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}
当时最稚嫩的代码。。。真的有种说不出的感动：
#include <iostream>
#include <queue>
using namespace std; const int maxn = + ;
const int maxm = + ; struct Edge
{
int from, to, cap, flow;
}; struct Dinic
{
int n, m, s, t;
int first[maxn], next[maxm]; Edge edges[maxm]; void init(int n)
{
this -> n = n;
m = ; memset(first, -, sizeof(first)); return ;
} void AddEdge(int from, int to, int cap)
{
edges[m] = (Edge){from, to, cap, };
next[m] = first[from];
first[from] = m++; edges[m] = (Edge){to, from, , };
next[m] = first[to];
first[to] = m++; return ;
} int d[maxn], cur[maxn];
bool vis[maxn]; int BFS()
{
memset(vis, , sizeof(vis));
queue<int> Q; Q.push(s);
vis[s] = true;
d[s] = ; while(!Q.empty())
{
int x = Q.front(); Q.pop(); for(int i = first[x]; i != -; i = next[i])
{
Edge& e = edges[i];
if(!vis[e.to] && e.cap > e.flow)
{
vis[e.to] = true;
d[e.to] = d[x] + ;
Q.push(e.to);
}
}
} return vis[t];
}
int DFS(int x, int a)
{
if(x == t || !a) return a; int f, flow = ; for(int& i = cur[x]; i != -; i = next[i])
{
Edge& e = edges[i];
if(d[e.to] == d[x] + && (f = DFS(e.to, min(a, e.cap - e.flow))) > )
{
flow += f;
a -= f;
e.flow += f;
edges[i ^ ].flow -= f;
if(!a) break;
}
}
return flow;
} int MaxFlow(int s, int t)
{
this -> s = s;
this -> t = t; int flow = ; while(BFS())
{
for(int i = ; i < n; i++) cur[i] = first[i];
flow += DFS(s, );
}
return flow; //你大爷！！！！！！！！！！！！！！！！
}
}sol; int a[][];
int nx[] = {, , -, };
int ny[] = {-, , , }; int main()
{
int n, m;
scanf("%d", &n); m = n; sol.init(n * m + ); long long double tot = ; int s = n * m;
int t = n * m + ; for(int i = ; i < n; i++)
for(int j = ; j < m; j++)
{
scanf("%d", &a[i][j]);
tot += a[i][j];
if((i + j) & )
{
sol.AddEdge(s, i * m + j, a[i][j]); for(int d = ; d < ; d++)
{
int mx = nx[d] + i;
int my = ny[d] + j; if(mx >= && mx < n && my >= && my < m)
{
sol.AddEdge(i * m + j, mx * m + my, );
}
}
}
else sol.AddEdge(i * m + j, t, a[i][j]);
} printf("%d\n", tot - sol.MaxFlow(s, t));
//system("pause");
return ;
}
搜索
复制