Language: C++

// Description: ??£?????°??????????????????????°??????\??????????????¨ 
// TimeComplexity: $ \mathcal{O}(V^3+ V^2 2^T + V3^T)$ T????????????????????°
// Verifyed: AOJ GRL_2_C todo

auto Dreyfus_wagner(const G &graph,const auto &term){
	using W=int; W inf=1<<28;
	const int n=graph.size(),t=term.size();
	if(t<=1) return 0;
	auto dist=graph;
	vector<vector<W>> opt(1<<t,vector<W>(n,inf));

	rep(k,n)rep(i,n)rep(j,n) chmin(dist[i][j],dist[i][k]+dist[k][j]);
	
	rep(i,t){
		rep(j,n) opt[1<<i][j]=dist[term[i]][j];
		rep(j,t) opt[(1<<i)|(1<<j)][term[j]]=dist[term[i]][term[j]];
	}

	auto next_combination=[&](int s){
		int x=s&-s,y=s+x;
		return ((s&~y)/x>>1)|y;
    };

	rep(k,2,t){
		for(int s=(1<<k)-1;s<(1<<t);s=next_combination(s)){
			rep(x,n){
				int ns=s,cur=-1;
				rep(i,t) if(term[i]==x) cur=i;
				if(cur!=-1) ns|=(1<<cur);
				if(cur!=-1 and s==ns) continue;
				for(int u=(s-1)&s;u!=0;u=(u-1)&s){
					int c=s&(~u);
					chmin(opt[ns][x],opt[u][x]+opt[c][x]);
				}
			}
			int x=s&-s,y=s+x;
			s=((s&~y)/x>>1)|y;
		}
		for(int s=(1<<k)-1;s<bit(1<<t);s=next_combination(s)){
			rep(x,n){
				int ns=s,nxt=-1;
				rep(i,t) if(term[i]==x) nxt=i;
				if(nxt!=-1) ns|=(1<<nxt);
				if(nxt!=-1 && s==ns) continue;
				rep(y,n) chmin(opt[ns][x],opt[s][y]+dist[y][x]);
			}
		}
	}

	const int mask=(1<<t)-1;
	W ans=opt[mask][0];
	rep(i,n) chmin(ans,p[mask][i]);
	return ans;
}

int main(void){
	int h,w;
	while(cin >> h >> w){
		if(h==0)
			break;
		rep(i,vmax)rep(j,vmax) d[i][j]=(i==j)?0:inf;
		V=h*w,T=0;

		rep(i,h*w){
			int in;
			cin >> in;
			if(in) t[T++]=i;
		}
		rep(i,h)rep(j,w){
			int cur=w*i+j;
			if(i+1<h) d[cur][cur+w]=d[cur+w][cur]=1;
			if(j+1<w) d[cur][cur+1]=d[cur+1][cur]=1;
		}
		int res=minimum_steiner_tree();
		cout << V-1-res << endl;
	}
	return 0;
}

// q[s|c][x]=min(q[s|c],p[s][x]+p[c][x]);
// p[s][x]=min(p[s][x],p[s][y]+d[y][x]) y???s
// p[s][x]=min(p[s][x],q[s][y]+d[y][x]) y???v/s

Compiler output:
a.cc:5:27: error: 'G' does not name a type
    5 | auto Dreyfus_wagner(const G &graph,const auto &term){
      |                           ^
a.cc:5:42: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
    5 | auto Dreyfus_wagner(const G &graph,const auto &term){
      |                                          ^~~~
a.cc: In function 'auto Dreyfus_wagner(const int&, const auto:1&)':
a.cc:7:27: error: request for member 'size' in 'graph', which is of non-class type 'const int'
    7 |         const int n=graph.size(),t=term.size();
      |                           ^~~~
a.cc:8:12: error: 't' was not declared in this scope
    8 |         if(t<=1) return 0;
      |            ^
a.cc:10:9: error: 'vector' was not declared in this scope
   10 |         vector<vector<W>> opt(1<<t,vector<W>(n,inf));
      |         ^~~~~~
a.cc:10:24: error: expected primary-expression before '>>' token
   10 |         vector<vector<W>> opt(1<<t,vector<W>(n,inf));
      |                        ^~
a.cc:10:34: error: 't' was not declared in this scope
   10 |         vector<vector<W>> opt(1<<t,vector<W>(n,inf));
      |                                  ^
a.cc:10:44: error: expected primary-expression before '>' token
   10 |         vector<vector<W>> opt(1<<t,vector<W>(n,inf));
      |                                            ^
a.cc:10:27: error: there are no arguments to 'opt' that depend on a template parameter, so a declaration of 'opt' must be available [-fpermissive]
   10 |         vector<vector<W>> opt(1<<t,vector<W>(n,inf));
      |                           ^~~
a.cc:10:27: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
a.cc:12:13: error: 'k' was not declared in this scope
   12 |         rep(k,n)rep(i,n)rep(j,n) chmin(dist[i][j],dist[i][k]+dist[k][j]);
      |             ^
a.cc:12:9: error: there are no arguments to 'rep' that depend on a template parameter, so a declaration of 'rep' must be available [-fpermissive]
   12 |         rep(k,n)rep(i,n)rep(j,n) chmin(dist[i][j],dist[i][k]+dist[k][j]);
      |         ^~~
a.cc:12:17: error: expected ';' before 'rep'
   12 |         rep(k,n)rep(i,n)rep(j,n) chmin(dist[i][j],dist[i][k]+dist[k][j]);
      |                 ^~~
      |                 ;
a.cc:14:13: error: 'i' was not declared in this scope
   14 |         rep(i,t){
      |             ^
a.cc:14:9: error: there are no arguments to 'rep' that depend on a template parameter, so a declaration of 'rep' must be available [-fpermissive]
   14 |         rep(i,t){
      |         ^~~
a.cc:14:17: error: expected ';' before '{' token
   14 |         rep(i,t){
      |                 ^
      |                 ;
a.cc:24:9: error: there are no arguments to 'rep' that depend on a template parameter, so a declaration of 'rep' must be available [-fpermissive]
   24 |         rep(k,2,t){
      |         ^~~
a.cc:24:19: error: expected ';' before '{' token
   24 |         rep(k,2,t){
      |                   ^
      |                   ;
a.cc:51:15: error: 'opt' was not declared in this scope
   51 |         W ans=opt[mask][0];
      |               ^~~
a.cc:52:9: error: there are no arguments to 'rep' that depend on a template parameter, so a declaration of 'rep' must be available [-fpermissive]
   52 |         rep(i,n) chmin(ans,p[mask][i]);
      |         ^~~
a.cc:52:17: error: expected ';' before 'chmin'
   52 |         rep(i,n) chmin(ans,p[mask][i]);
      |                 ^~~~~~
      |                 ;
a.cc: In function 'int main()':
a.cc:58:15: error: 'cin' was not declared in this scope
   58 |         while(cin >> h >> w){
      |               ^~~
a.cc:61:21: error: 'i' was not declared in this scope
   61 |                 rep(i,vmax)rep(j,vmax) d[i][j]=(i==j)?0:inf;
      |                     ^
a.cc:61:23: error: 'vmax' was not declared in this scope
   61 |                 rep(i,vmax)rep(j,vmax) d[i][j]=(i==j)?0:inf;
      |                       ^~~~
a.cc:61:17: error: 'rep' was not declared in this scope
   61 |                 rep(i,vmax)rep(j,vmax) d[i][j]=(i==j)?0:inf;
      |                 ^~~
a.cc:62:17: error: 'V' was not declared in this scope
   62 |                 V=h*w,T=0;
      |                 ^
a.cc:62:23: error: 'T' was not declared in this scope
   62 |                 V=h*w,T=0;
      |                       ^
a.cc:74:25: error: 'minimum_steiner_tree' was not declared in this scope
   74 |                 int res=minimum_steiner_tree();
      |                         ^~~~~~~~~~~~~~~~~~~~
a.cc:75:17: error: 'cout' was not declared in this scope
   75 |                 cout << V-1-res << endl;
      |                 ^~~~
a.cc:75:36: error: 'endl' was not declared in this scope
   75 |                 cout << V-1-res << endl;
      |                                    ^~~~