Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 2363  Solved: 1092

Description

Input

Output

仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。

Sample Input

3 2

10 0

20 0

-10 0

-5 1 0 0

100 1 2 1

100 0

Sample Output

25

HINT

在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。 

一个方案为，首先进攻P1,1, P0,1，此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。 

【大致数据规模】

约20%的数据满足1 ≤ N, M ≤ 5；

约40%的数据满足1 ≤ N, M ≤ 10；

约100%的数据满足1 ≤ N ≤ 20，1 ≤ M ≤ 30，-10000 ≤ Score ≤ 10000 。

Source

 

网络流+拓扑排序

因为植物可能会互相保护而形成环，所以先用拓扑排序排除环，求出图中的闭合子图。

然后按照先吃右边才能吃左边的关系，从每个点向它左边一格的点连边，容量为INF

保护型的植物向它保护的植物连边，容量为INF。

吃植物能获得收益时，该植物向汇点连边，容量为收益。

吃植物需要代价时，源点向该植物连边，容量为代价的绝对值。

答案=可能获得的收益总和-最小割。

 

1 /*by SilverN*/  2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6 #include
         
            7 #include
          
            8 #include
           
             9 using namespace std; 10 const int mx[5]={ 0,1,0,-1,0}; 11 const int my[5]={ 0,0,1,0,-1}; 12 const int INF=1e9; 13 const int mxn=2010; 14 int read(){ 15 int x=0,f=1;char ch=getchar(); 16 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 17 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 18 return x*f; 19 } 20 struct edge{ 21 int v,nxt,f; 22 }e[mxn*500]; 23 int hd[mxn],mct=1; 24 void add_edge(int u,int v,int f){ 25 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=f;hd[u]=mct;return; 26 } 27 void insert(int u,int v,int f){ 28 add_edge(u,v,f);add_edge(v,u,0);return; 29 } 30 vector
            
             eg[mxn]; 31 int n,m,S,T; 32 int d[mxn]; 33 bool BFS(){ 34 memset(d,0,sizeof d); 35 queue
             
              q; 36 d[S]=1; 37 q.push(S); 38 while(!q.empty()){ 39 int u=q.front();q.pop(); 40 for(int i=hd[u];i;i=e[i].nxt){ 41 int v=e[i].v; 42 if(e[i].f && !d[v]){ 43 d[v]=d[u]+1; 44 q.push(v); 45 } 46 } 47 } 48 return d[T]; 49 } 50 int DFS(int u,int lim){ 51 if(u==T)return lim; 52 int f=0,tmp; 53 for(int i=hd[u];i;i=e[i].nxt){ 54 int v=e[i].v; 55 if(d[v]==d[u]+1 && e[i].f && (tmp=DFS(v,min(lim,e[i].f)))){ 56 e[i].f-=tmp; e[i^1].f+=tmp; 57 f+=tmp; lim-=tmp; 58 if(!lim)return f; 59 } 60 } 61 d[u]=0; 62 return f; 63 } 64 int Dinic(){ 65 int res=0; 66 while(BFS())res+=DFS(S,INF); 67 return res; 68 } 69 int id[50][50],cnt=0,ed; 70 void init(){ 71 for(int i=1;i<=n;i++) 72 for(int j=1;j<=m;j++) 73 id[i][j]=++cnt; 74 ed=n*m; 75 return; 76 } 77 int sc[mxn]; 78 int ind[mxn]; 79 int st[mxn],top=0; 80 bool vis[mxn]; 81 void topo(){ //拓扑排序，判断植物能否攻击 82 int i,j,res=0; 83 for(i=1;i<=cnt;i++) 84 if(!ind[i])st[++top]=i; 85 while(top){ 86 int u=st[top--]; 87 vis[u]=1; 88 if(sc[u]>0){ 89 res+=sc[u]; 90 insert(u,T,sc[u]);//可能得到的分数 91 } 92 else insert(S,u,-sc[u]);//需要付出的代价 93 for(j=0;j
              
               1){ //先解锁右面的才能吃左面的 124 eg[id[i][j]].push_back(id[i][j-1]);125 ind[id[i][j-1]]++;126 }127 }128 }129 topo();130 return 0;131 }