According to Microsoft, if a flow is triggered by a premier connector the Power Apps Premier or D365 license are valid, and there's no need to associate with an app. However, if you have triggers like scheduler or https, then theoretically you would need to purchase the Power Automate Premium license.
This does not make any sense, as we have a lot of scheduled jobs or triggered by buttons on the Command Bar.
So apparently this is the workaround, however I don't understand how this prevent people from associate all the flows to an existing app.