1324: Exca王者之剑

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 483  Solved: 248

[][][]

Description

 

Input

第一行给出数字N,M代表行列数.N,M均小于等于100 下面N行M列用于描述数字矩阵

Output

输出最多可以拿到多少块宝石

Sample Input

2 2

1 2

2 1

Sample Output

4

HINT

Source

Solution

最小割裸模型

见棋盘直接黑白染色，偶数秒发生消失？那就偶数秒和奇数秒分开二分图建图即可

Code

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    int 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*10+ch-'0'; ch=getchar();}    return x*f;}#define maxm 1000010#define maxn 10010int n,m,tot;struct EdgeNode{
    int next,to,cap;}edge[maxm];int head[maxn],cnt=1;void add(int u,int v,int w){    cnt++;    edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].cap=w; edge[cnt].to=v;}void insert(int u,int v,int w) {add(u,v,w); add(v,u,0);}int val[110][110];int dis[maxn],que[maxn<<1],cur[maxn],S,T;bool bfs(){    for (int i=S; i<=T; i++) dis[i]=-1;    que[0]=S; dis[S]=0; int he=0,ta=1;    while (he
          
           =1) insert(locate(i,j),locate(i-1,j),inf);                    if (j+1<=m) insert(locate(i,j),locate(i,j+1),inf);                    if (j-1>=1) insert(locate(i,j),locate(i,j-1),inf);                }            else insert(locate(i,j),T,val[i][j]);    int maxflow=dinic();    printf("%d\n",tot-maxflow);    return 0;}
          
         
        
       
      

微机课随随便便打着玩系列，被旁边同学摁了个数，然后第一遍还WA了...纸张